Authors Title Abstract
Jaroslav Fowkes, Coralia Cartis A block-coordinate Gauss-Newton method for nonlinear least squares We propose a block-coordinate Gauss-Newton method for nonlinear (nonconvex) least squares problems that computes Jacobians only on a subset of the optimization variables at a time. We investigate globalising this approach using either a regularization term or a trust-region model and show global complexity results as well as extensive computational results on CUTEst test problems. Furthermore, as our approach exhibits very slow rates of convergence on certain nonconvex problems, we design adaptive block size variants of our methods that can overcome these difficulties.
Geovani Grapiglia A refined worst-case complexity analysis for non-monotone line searches A non-monotone line search framework has been proposed by Sachs and Sachs (2011) for smooth unconstrained optimization problems, generalizing several non-monotone stepsize rules. More recently, worst-case complexity bounds to achieve approximate first-order optimality were proved by Grapiglia and Sachs (2017) for this framework under the assumption that the sequence of parameters that control the non-monotonicity is summable. In this work, we relax this assumption in various ways and provide complexity estimates for the resulting non-monotone schemes, as well as preliminary numerical results.
Luigi Carratino, Alessandro Rudi, Lorenzo Rosasco Algorithmic Regularization for Machine Learning Classically in machine learning, regularization is achieved imposing explicit constraints on a data fit term, and optimization aspects are considered separately. In this talk we discuss how regularization can be controlled implicitly by an optimization method of choice. This latter approach has the advantage that training time controls at the same time statistical accuracy and time complexity of the obtained estimator. Moreover, we discuss how computations can be further reduced considering random projections. Our study bridges optimization and statistical studies.
Olivier Fercoq, Ahmet Alacaoglu, Ion Necoara, Volkan Cevher Almost surely constrained convex optimization We propose a stochastic gradient framework for solving stochastic composite convex optimization problems with (possibly) infinite number of linear inclusion constraints that need to be satisfied almost surely. We use smoothing and homotopy techniques to handle constraints without the need for matrix-valued projections. We show for our stochastic gradient algorithm O(log(k)/sqrt(k)) convergence rate for general convex objectives and O(log(k)/k) convergence rate for restricted strongly convex objectives. These rates are known to be optimal up to logarithmic factors, even without constraints.
Nikita Doikov, Yurii Nesterov Complexity of Cubically Regularized Newton Method for Minimizing Uniformly Convex Functions In this paper we study iteration complexity of cubically regularized proximal Newton method for solving composite minimization problems with uniformly convex objective. We introduce the notion of second-order condition number of a certain degree and present the linear rate of convergence in a nondegenerate case.
The algorithm automatically achieves the best possible global complexity bound among different problem classes of functions with Holder continuous Hessian of the smooth part.
The research results of this paper were obtained with support of ERC Advanced Grant 788368.
Adilet Otemissov, Coralia Cartis Dimensionality reduction techniques for global optimization We show that the scalability issues of Global Optimisation algorithms can be alleviated for functions with low effective dimensionality; these appear in various applications, e.g. neural networks and engineering simulations. We propose the use of random subspace embeddings within any global minimisation algorithm, extending Wang et al.’s approach. We investigate the efficacy and convergence of the method in its static and adaptive formulations, respectively. Using popular global solvers, we illustrate our algorithmic proposals/theoretical findings numerically. Joint work with Coralia Cartis.
Anton Rodomanov, Yurii Nesterov Greedy Quasi-Newton Method with Explicit Superlinear Convergence We propose a new quasi-Newton method for unconstrained minimization of smooth functions. Our method is based on the famous BFGS scheme but it uses a greedily selected coordinate vector for updating the Hessian approximation instead of the previous search direction. We prove that the proposed method has local superlinear convergence and establish a precise bound for its rate. To our knowledge, this result is the first explicit non-asymptotic rate of superlinear convergence for quasi-Newton methods. The research results of this paper were obtained with support of ERC Advanced Grant 788368.
Lindon Roberts, Coralia Cartis, Jan Fiala, Benjamin Marteau Improving the scalability of derivative-free optimization for nonlinear least-squares problems In existing techniques for model-based derivative-free optimization, the computational cost of constructing local models and Lagrange polynomials can be high. As a result, these algorithms are not as suitable for large-scale problems as derivative-based methods. In this talk, I will introduce a derivative-free method based on exploration of random subspaces, suitable for nonlinear least-squares problems. This method has a substantially reduced computational cost (in terms of linear algebra), while still making progress using few objective evaluations.
Francesco Tudisco, Andrea Cristofari, Francesco Rinaldi Leading community detection in networks via total variation optimization Maximizing the modularity of a network is a successful means to identify an important community of nodes. However, this combinatorial optimization problem is NP-hard. We use what we call Modularity Total Variation (MTV) to formulate a box-constrained continuous optimization problem whose solution coincides with the original discrete one. Thus we propose a fast active-set based method to optimize the MTV. Extensive experiments show that the method compares favorably with state-of-the-art alternatives such as standard matrix methods and the GenRDCA approach for nonlinear modularity eigenvectors.
John Pearson Numerical Linear Algebra for PDE-Constrained Optimization Problems Arising from Biological Mechanisms The derivation and implementation of bespoke linear algebra methods is essential when tackling huge-scale matrix systems arising from PDE-constrained optimization problems. We consider the development of fast and feasible preconditioned iterative solvers for such problems, focusing on applications from pattern formation processes and chemotaxis mechanisms. To tackle the large and sparse matrix systems that arise from discretization of the nonlinear PDEs involved, we exploit the saddle point structure of the matrices, and develop potent approximations of the (1,1)-block and Schur complement.
Michal Kocvara On barrier and modified barrier multigrid methods for 3d topology optimization Topology optimization of mechanical structures is a challenging problem due to its very large dimension easily reaching millions of variables. We propose to solve it by the Penalty-Barrier Multiplier (PBM) method, originally introduced by R. Polyak and later studied by Ben-Tal and Zibulevsky and others. Using the structure of the Hessian of the generalized augmented Lagrangian, we will solve the arising linear systems by the multigrid method. We will demonstrate that our algorithm outperforms interior point multigrid method, as well as the established OC method with multigrid solver.
Dmitri Kvasov, Yaroslav Sergeyev, Marat Mukhametzhanov On numerical testing of black-box global optimization methods Multidimensional constrained black-box global optimization problems are considered in this talk. Various aspects of numerical comparison of deterministic and stochastic methods for solving these challenging problems are investigated. A novel methodology to verify the methods performance is discussed which is based on the operational zones and aggregated operational zones recently proposed by the authors. This methodology is then illustrated on testing some known global optimization methods with the usage of the GKLS-generators of test classes.
Margherita Porcelli, Philippe L. Toint On the use of interpolation models in the solution of structured optimization problems with BFO The talk will introduces techniques that allow the solution of large structured optimization problems in the context of random pattern search in nonlinear optimization.  They result from a re-interpretation of techniques proposed by Price and Toint, but introduce some significant new ideas which prove to be very efficient. Also, polynomial interpolation models will be adapted to the partial separable case and employed through the exploitation of the search step feature. A numerical discussion of these features embedded in a new BFO version will be presented.
Coralia Cartis Stochastic optimization – with complexity guarantees Classical optimization methods are challenged by the scale of machine learning applications and the lack of /cost of full derivatives, as well as the stochastic nature of the problem. On the other hand, the simple approaches that the machine learning community uses need improvement. Here we try to merge the two perspectives and adapt the strength of classical optimization techniques to meet the challenges of data science applications: from deterministic to stochastic problems, from small to large scale.
Francesco Rinaldi, Immanuel Bomze, Samuel Rota Bulò Support identification in finite time with convergent Frank-Wolfe variants We focus on the problem of minimizing a non-convex function over the unit simplex. We analyze two well-known and widely used variants of the Frank-Wolfe algorithm and first prove global convergence of the iterates to stationary points both when using exact and Armijo line search. Then we show that the algorithms identify the support in a finite number of iterations. This, to the best of our knowledge, is the first time a manifold identification property has been shown for such a class of methods.
Manuel V. C. Vieira A bi-level container loading problem In this talk we present a multi-container loading problem with 3-open dimensions, whose correct formulation is a bi-level mixed-integer nonlinear program. At the same time, this is motivated by a real-world application. We also give a reformulation of the problem as a parametric mixed-integer nonlinear program and we prove that the bi-level container loading problem is  NP-hard.
We also present an algorithm and its efficiency is demonstrated with numerical experiments.
Mathieu Besançon, Miguel F. Anjos, Luce Brotcorne Near-optimal robust bilevel optimization Bilevel optimization is a paradigm that integrates the optimal response to a lower-level optimization problem as a constraint of an upper-level problem. We introduce near-optimal robustness for bilevel problems, building on existing concepts from the literature. This generalizes the pessimistic approach, protecting the upper-level decision-maker from limited deviations in the lower-level. This can be interpreted in various settings modelled using bilevel optimization. We develop a duality-based formulation in the case of a convex lower-level problem, leveraging tools from robust optimization.
Anton Svensson, Abderrahim Hantoute Weak Fuzzy Subdifferential Calculus Rules and Application to Bilevel Programming Problems Weak fuzzy subdifferential calculus rules have an advantage over the exact ones because they do not require any qualification condition, in the context of lower semicontinuous data defined on Asplund spaces. We give some improvements on these rules, for instance, on non-degenerate fuzzy optimality conditions and on the estimation of the subdifferential of a supremum of lower semicontinuous functions. Our work brings novelty even in finite dimensions. As an application, we give fuzzy (necessary) optimality conditions for a bilevel programming problem in finite dimensions.
Tobias Seidel, Karl-Heinz Küfer A class of adaptive discretization methods solving semi-infinite programming problems (SIPs) with quadratic rate of convergence A classic solution approach for semi-infinite programming is based on discretizing the semi-infinite index set. One can observe in practice that for many problems convergence can be improved by adding the solutions of the lower level problems to the discretization. In this talk, we will present results proving a quadratic rate of convergence for an adaptive discretization algorithm, which explains the improved convergence properties.
Besides the theoretical concepts the talk will address several domains of applications the Fraunhofer Institute for Industrial Mathematics is working on.
Alemseged Gebrehiwot Weldeyesus, Jacek Gondzio Column generation and warm-starting in semidefinite programming We apply IPMs to solve large-scale semidefinite programming problems arising from optimization of truss structures with stability constraints. We employ a technique, equivalent to column generation in linear programming, where a sequence of smaller subproblems is solved, ultimately producing the solution of the original problem. Whenever successive subproblems display any exploitable similarity, the warm-starting strategy is applied. We report on numerical experiments to validate the column generation technique and demonstrate the efficiency of the warm-start strategy on large problems
Paula Amaral, Immanuel Bomze Copositivity detection using DNN decomposition Copositivity plays an important role in optimization, particularly in discrete and quadratic optimization, since many of these problems admit a conic reformulation, or, at least, a relaxation over the completely positive cone and by duality we obtain a related conic problem over the copositive cone.  Copositivity detection is difficult; in particular, to decide if it is not copositive is NP-complete. In this talk we present an algorithm that is based on the decomposition of a matrix in the doubly non-negative cone and present computational results for a set of Dimacs challenge instances.
Lucas Letocart, Enrico Bettiol, Immanuel Bomze, Francesco Rinaldi, Emiliano Traversi Dantzig-Wolfe reformulation and Completely Positive relaxation for binary QCQPs We consider the problem of minimizing a general quadratic objective function with quadratic constraints and binary variables. We relax the constraint linking matrix X to the original variables x and propose a column generation method based on Dantzig-Wolfe Reformulation that leads to a linear master and an unconstrained 0-1 pricing problem. We show that the domain of this relaxation is contained in the cone of Completely Positive matrices, hence it provides us with a tighter lower bound than the SDP one. We provide computational results in support to our algorithm, for all settings considered.
Immanuel Bomze, Werner Schachinger, Jorgen Weibull Towards responsible game theory – from Kant to a copositive view on a parametric QP In game theory, players are usually assumed to choose their strategies exclusively in terms of their own benefit. Recent work (Alger/Weibull, Econometrica 2013) considers morally motivated agents whose objective  partly includes social welfare if everybody would do likewise, as in Immanuel Kant’s categorical imperative (1785). This results in a QP parametrized by strategies. Using conic optimality conditions, we characterize existence of Nash equilibrium. For partnership games, this new concept yields an interesting intermediate solution between global and local optimality for the Standard QP.
Markus Gabl Uncertainty-Aversion-Measures in Robust Linear Optimization with Endogenous Uncertainty In recent literature decision dependent uncertainty-sets were introduced in order to model the trade-off between reducing the cost of robustness versus the cost of reducing uncertainty. Inspired by risk-aversion-measures, we introduce uncertainty-aversion-measures (UAM) which model the trade-off between worst case performance and uncertainty of performance in case of such endogenous uncertainty. We present ways to formalize UAMs in mathematical models, and derive reformulations/approximations solvable by standard methods. The workhorse is mixed-integer linear and conic optimization.
VAN HUNG NGUYEN An Optimal Controller for Ship Main Engines Considering Ship Motions Main engines are used for ship propulsion, but ship main engines’ speeds are strongly influenced by the ships’ motions, especially in heavy seas. This study constructs an optimal controller for ship main engine considering both fuel supply regulation, and ship motions. A Multivariate Auto Regressive model was used for governor-engine system based on statistical analysis, and then a new optimal controller applying modern control theory was designed by considerating ship’s longitudinal motion. Effectiveness of this optimal controller is shown clearly by results of full-scale experiments.
Eloisa Macedo, Ricardo Tomás, Paulo Fernandes, Margarida Coelho, Jorge Bandeira Multi-criteria road traffic assignment with sustainability concerns Traffic congestion is a serious problem in roads. Sustainable travel behaviour can be considered a solution that influences drivers’ decisions by balancing economic, social and environmental objectives. The aim of this study is to develop a multi-criteria traffic assignment model to alleviate traffic congestion, in which drivers and traffic planner perspectives are met by minimizing travel time, fuel consumption and emissions (global and local pollutants). It can improve decision making, particularly for strategic policy making and planning, and road users’ awareness of their route choice.
Niall Morrison, Edmondo Minisci, Annalisa Riccardi Multi Objective Optimisation of Fluid Devices by Multi Fidelity Modelling Design optimisation is essential for the design of complex fluid devices to ensure adequate performance for all operating conditions. However, conducting this optimization with high fidelity models, which are necessary to fully describe the physical conditions of the system, leads to too high computational costs. To tackle this problem, a multi-fidelity model management framework is proposed. This approach combines the results of models at different levels such that an optimal design can be found at minimal costs.
Linas Litvinas, Antanas Zilinskas A Bayesian Algorithm of Global Multiobjective Optimization An algorithm for non-convex multi-objective optimization is proposed implementing ideas of Bayesian approach to global optimization. The proposed algorithm is a generalization of the recently proposed modification of the P-algorithm aimed at non-convex single-objective optimization problems. The computational challenges of known implementations of Bayesian algorithms are circumvented using a specially developed statistical model of the aimed objective functions. The performance of the proposed algorithm is demonstrated by applications to optimal design of biosensors and bioreactors.
Gabriele Eichfelder, Marianna De Santis, Julia Niebling, Stefan Rocktäschel A Decision Space Method for Mixed-Integer Convex Multiobjective Optimization We propose a method for solving mixed-integer convex multiobjective optimization problems. The algorithm determines a covering of the efficient set. It uses a partitioning of the feasible set in the pre-image space. For discarding, lower and upper bounds are used. Lower bounds are obtained by outer approximations of the nondominated set of sub-problems using ideas from Benson’s algorithm. In contrast to criterion space methods, our approach can easily be generalized to an arbitrary number of objective functions. By using convex underestimators, it can also be extended to nonconvex problems.
Marco Milano, Kathrin Klamroth Active Sets and a Generalized Weight Space Decomposition for Multiobjective Convex Quadratic Programming Problems We investigate the representation of efficient solutions of multiobjective convex quadratic programming problems with linear constraints using the weighted sum scalarization and the concept of a weight space decomposition by active sets, similar to Goh and Yang (1996). We derive some properties of the weight space decomposition using multiobjective and parametric optimization theory. Moreover, we present two special cases for which the weight cells are convex polyhedra. We conclude with an investigation of a particularly structured case with applications in location theory.
Firdevs Ulus, Cagin Ararat, Muhammad Umer An Approximation Algorithm for Convex Vector Optimization Problems with Norm Minimizing Scalarizations We study Benson-type approximation algorithms for convex vector optimization problems. In general, these algorithms solve a Pascoletti-Serafini (PS) scalarization in each iteration. PS model has two parameters: a reference point and a direction vector. The structure of a Benson-type algorithm gives a clear way of choosing a reference point. However, there are different approaches to choose a direction parameter and this choice affects the performance of the algorithm. We propose a Benson-type algorithm that solves norm-minimizing scalarizations which do not require a direction parameter.
Katrin Teichert, Kerstin Daechert An improved hyperboxing algorithm for calculating a Pareto front representation We use the improved update of the inner and, analogously, outer approximation presented in the previous talk within a novel sandwich algorithm for multi-objective non-linear optimization problems. Since the part of the outcome set that is sandwiched between inner and outer approximation can be represented as a union of rectangular sets, we call this general sandwich approach hyperboxing algorithm. We present the main ingredients of such an algorithm and show improvements with respect to the computational time. Our numerical results are based on test problems with up to 10 objectives.
Kerstin Daechert, Katrin Teichert Efficient update of the inner and outer approximation of multi-objective non-linear optimization problems A popular way to solve continuous multi-objective optimization problems is to compute an inner and an outer approximation to sandwich the Pareto front.
While particular sandwich algorithms exist for convex problems, we can also define a very general sandwich algorithm in the non-convex case by only using the properties of non-dominance.Recently, improved techniques have been proposed to update the inner approximation in the discrete case which can be translated directly to the continuous case. We present the general idea as well as implementational variants.
Hiroki Tanabe, Ellen Hidemi, Fukuda Nobuo Yamashita Multiobjective proximal gradient methods and application to robust multiobjective optimization In this work, we first extend single-objective proximal gradient methods to multiobjective optimization. We then show the global convergence of the proposed methods, that is, we prove that all accumulation points of the sequences generated by these algorithms, if they exist, are Pareto stationary. Finally, we apply the proposed algorithms to robust multiobjective optimization problems, which are problems with uncertainties. Under some assumptions, we show that we can convert their subproblems to computationally tractable problems.
Julia Niebling, Gabriele Eichfelder, Kathrin Klamroth Solving Optimization Problems with Nonconvex Constraints by Using Multiobjective Optimization A multiobjective optimization problem is often solved by using techniques from single objective optimization. There, a series of associated scalarizations are formulated and solved by well-known methods from single objective optimization. Conversely, it is also possible to use tools for multiobjective optimization and some suitable filtering techniques to solve a single objective problem. This shows that both topics have relevant relations. In this talk, that relationship is further considered and we present a new branch-and-bound algorithm, which uses this relationship to solve single object
Frédéric Messine, Sonia Cafieri, Loïc Cellier, Riadh Omheni Combination of optimal control approaches for aircraft conflict avoidance via velocity regulation We propose an optimal control model for the problem of aircraft conflict avoidance, where aircraft separation is achieved by changing the speeds of aircraft, and the integral over a time window of their squared accelerations is minimized. We propose an original decomposition of the problem into 3 zones, in such a way that in two of them, no conflict occurs. Then, using the Pontryagin maximum principle, 2 new formulations of the original optimal control problem are proposed and solved via direct shooting methods. Numerical results show the effectiveness of the proposed approaches.
Francesco Marchetti, Edmondo Minisci, Annalisa Riccardi Trajectory Optimization of a Reusable Launch Vehicle. A comparison between different direct trajectory optimization methods for a Single Stage to Orbit Reusable Launch Vehicle is carried out and presented. Collocation and multiple-shooting approaches are compared in terms of accuracy, scalability, computational costs, and sensitivity to irregularities of models. The ascent trajectory optimization of the FESTIP-FSS5 Reusable Launch Vehicle is considered.
Ioannis Baltas, Athanasios Yannacopoulos Applications of Robust Control in Finance, Insurance and Risk Management Stochastic optimal control is an indispensable part of mathematical economics and modern financial risk management. However, despite its importance and wide range of applicability, it suffers for a serious limitation since it does not incorporate model uncertainty aspects, a key factor when it comes to realistic modeling. The necessary framework to surpass this obstacle is provided by robust control theory. The present work is devoted to the applications of robust stochastic optimal control in the study of problems arising in Finance, Insurance and Risk management.
Esma Gaygisiz, Abdullah Karasan LIQUIDITY AUGMENTED ASSET PRICING VOLATILITY MODEL WITH JUMPS The importance of the liquidity has been highlighted and has been gaining much attention since global mortgage crisis outbroken in 2007-2008. During this crisis, most of the giant financial institutions hit hard by liquidity pressures and this directed regulatory authorities to take important measures. This study augments Bates (1996) stochastic volatility model with jumps to incorporate liquidity using Cox, Ingersoll and Ross (1985) model. The liquidity augmented model in the study outperformed other models in prediction and revealed the importance of liquidity.
Yosefat Nava-Alemán, Viacheslav Kalashnikov, Nataliya Kalashnykova Natural Gas Cash-Out Problem Treated by Bilevel Optimal Control Bilevel programs are hierarchical optimization problems in the sense that their constraints are defined in part by a second parametric optimization problem. Hierarchical structures can be found in diverse scientific disciplines including environmental studies, classification theory, databases, network design, transportation, game theory, economics, and new applications, such as the gas cash-out problem. In its turn, this stimulates the development of both new theoretical results and efficient algorithms to solve bilevel programming problems.
José G. Flores-Muñiz, Viacheslav Kalashnikov, Nataliya Kalashnykova On Consistent Conjectural Variations Equilibrium in the Oligopoly Model According to the concept of conjectural variations equilibrium (CVE), the oligopoly agents behave as follows: each agent chooses his/her most favorable action taking into account that every rival’s strategy is a conjectured function of his own strategy.
The main obstacle in the way of admitting this concept is its consistency. The equilibrium is consistent if the conjectural best response of each agent coincides with his conjectured reaction function. However, such a definition does not work if the number of players is greater than two (since the coincidence is impossible).
Nuno Azevedo, Diogo Pinheiro, Susana Pinheiro Optimal Control of Semi-Markov Modulated SDEs We consider a stochastic optimal control problem with state variable dynamics described by a stochastic differential equation of diffusive type modulated by a semi-Markov process with a finite state space. Within such setup, we characterize the value function both in terms of a dynamic programming principle, and as the unique viscosity solution of a Hamilton-Jacobi-Bellman type equation. We conclude with an application to Mathematical Finance: the generalization of Merton’s optimal consumption-investment problem to financial markets exhibiting semi-Markov switching.
Alexander Zaslavski Optimal control problems arising in the forest management In this talk we study the forest management problem using the approach introduced and employed in our recent research and show the existence of turnpike properties and solutions of the corresponding infinite horizon problems.
Gerhard-Wilhelm Weber, Emel Savku, Ioannis Baltas Stochastic optimal control and games in a world of regime switches, paradigm shifts, jumps and delay We contribute to modern OR by hybrid (continuous-discrete) dynamics of stochastic differential equations with jumps and their optimal control. These systems allow for the representation of random regime switches or paradigm shifts, and are of growing importance in science, finance, economics, medicine and engineering. We introduce several new approaches to this area of stochastic optimal control and present results. These are analytical, finding of optimality criteria, closed-form or numerical solutions. We discuss the occurrence of delay, partial information and games, and give examples.
Giorgia Oggioni, Luis Baringo, Luigi Boffino An adaptive robust optimization approach for expansion planning of a small size electric energy system with electric vehicles and renewable units We propose an adaptive robust optimization approach for the expansion of a small size electricity system problem. This involves the construction of candidate renewable gen-erating units, storage units and charging stations for electric vehicles (EVs). The problem is formulated under the perspective of a central planner, which aims at determining the expansion plan that minimizes both investments and operation costs, including the power bought from the main grid. Both long-term uncertainty and short-term variability are considered.  The model is tested using an illustrative example.
Thomas Ashley, Emilio Carrizosa, Enrique Fernández-Cara Dynamic Optimisation Applied to Solar Power Tower Plants The distribution of temperature on an SPT plant receiver directly affects the lifespan of the structure and energy generated by the plant. Temperature peaks and uneven distributions can be caused by the aiming strategy enforced on the heliostat field. In this work, a continuous optimised aiming strategy is extended to consider a dynamic case, where the maximisation of energy gained whilst maintaining a homogeneous flux distribution is considered. Two dynamic constraints are then considered, and two algorithms presented to solve the problem, followed by a numerical illustration.
Miguel F. Anjos, Christian Bingane, Sébastien Le Digabel Tight-and-Cheap Conic Relaxations for AC Optimal Power Flow and Optimal Reactive Power Dispatch The classical alternating current optimal power flow problem is nonconvex and generally hard to solve. We propose a new conic relaxation obtained by combining semidefinite optimization with RLT. The proposed relaxation is stronger than the second-order cone relaxation, nearly as tight as the standard semidefinite relaxation, and up to one order of magnitude faster than for the semidefinite chordal approach on benchmarks with up to 6515 nodes. We extend the approach to optimal reactive power dispatch with similar results and performance.
Mauro Passacantando, Stefano Lucidi, Francesco Rinaldi A global optimization approach for solving non-monotone equilibrium problems A global optimization approach for solving non-monotone equilibrium problems (EPs) is proposed. The regularized gap functions are used to reformulate any EP as a constrained global optimization program and some bounds on the Lipschitz constant of such functions are provided. The proposed approach combines exact penalty functions with an improved version of the DIRECT algorithm which exploits local bounds of the Lipschitz constant. Unlike most existing methods, no monotonicity condition is assumed. Preliminary numerical results on several classes of EPs show the effectiveness of the approach.
Elisabetta Allevi, Adriana Gnudi, Igor Konnov, Giorgia Oggioni A sequential optimization model for municipal solid waste management We propose a sequential model to analyze a sustainable supply chain where waste is collected by city municipalities and it is partially reused by a recycling company for the production of new goods.
In this framework, the municipalities choose the prices at which they can offer waste to the recycling company, which, in turn, selects the processing volumes depending on these offer prices.
In order to find the equilibrium of the whole supply chain, we propose an iterative method that account for the sequence of the decision taken by the municipalities and the recycling company.
Juan Enrique Martínez-Legaz, Lionel THIBAULT A subdifferential characterization of Motzkin decomposable functions We provide a new subdifferential characterization for Motzkin decomposable (convex) functions. This characterization leads to diverse stability properties for such a decomposability for operations like addition and composition.
Cornel Pintea Closed convex sets with an open or closed Gauss range We characterize the closed convex subsets of the Euclidean space which have open or closed Gauss ranges. Some special attention is paid to the epigraphs of the lower semicontinuous convex functions (Based on a joint work with Juan Enrique Martínez-Legaz)
Giancarlo Bigi, Mauro Passacantando Differentiated oligopolistic markets with concave cost functions via Ky Fan inequalities A Nash–Cournot model for oligopolistic markets with concave cost functions and a differentiated commodity is analyzed. Equilibrium states are characterized through Ky Fan inequalities. Relying on the minimization of a suitable merit function, a general algorithmic scheme for solving them is provided. Two concrete algorithms are therefore designed that converge under suitable convexity and monotonicity assumptions. The results of  numerical tests on randomly generated markets are reported, trying to address the effect of differentation in scenarios with both high and low quality producers.
Miroslav Rada, Michal Cerny, Milan Hladik Efficient algorithms for rank estimators in robust regression The talk is devoted to efficient algorithms for evaluating so-called rank estimator in robust linear regression. Rank estimator is an estimator that minimizes a weighted sum of residuals, where weights depend on the ordering (ranks) of the residuals with respect to their values. We consider two cases and propose efficient algorithm for them: the general nonconvex case; and also a convex case covering the setup common in statistics: weights are determined by a function increasing in the rank of a residual; the function is the same for all the orderings of the residuals.
Marco A. López-Cerdá, Alexander Kruger, Xiaoqi Yang, Jiang Xing Zhu Hölder calmness in convex semi-infinite optimization This talk is focused on convex semi-infinite optimization, and provides a characterization of the Hölder calmness of the optimal set mapping, by showing its equivalence with the Hölder calmness of a certain (lower) level set mapping. This main result is key in providing estimates of the modulus of Hölder calmness of the argmin mapping under some particular conditions.
Xiaoqi Yang Piecewise Linear Vector Programs In general normed spaces, we classify piecewise linear functions and provide their representations using linear functions. Based on such classification and representations, we study a fully piecewise linear vector optimization (PLP) with the objective and constrained functions are piecewise linear. We divide (PLP) into some linear subproblems. Under some mild assumptions, we prove that the weak Pareto solution set of (PLP) is the union of finitely many polyhedra, each of which is a weak Pareto face (or a subset of a weak Pareto face) of some linear subproblem.
Wenfang Yao, Xiaoqi Yang Stability of Feasible Set Mapping of Linear System with Sparsity Constraint In this talk, we will mainly analyze the stability of a linear system under different types of perturbations in the perspective of the Aubin property. Additionally, a sparsity constraint is also considered. The main tool employed is the Mordukhovich criterion, with which we proposed a sufficient and necessary condition for the Aubin property of the solution to the system. Moreover, we also give some applications and examples for illustrations.
Marc Lassonde Subdifferential stability and subdifferential sum rules In the first part, we discuss the stability of the strong slope and of the subdifferential of a lower semicontinuous function with respect to Wijsman perturbations of the function, i.e. perturbations described via Wijsman convergence.
In the second part, we show how subdifferential sum rules can be viewed as special cases of subdifferential stability results.
Rossana Riccardi, Elisabetta Allevi Water investment planning: an optimization model for assessing efficiency and sustainability This work presents an investment decision-making tool to identify a portfolio of sustainable efficiency improvements, flood control investments that the market regulator authority can implement pursuing the objective of minimizing water shortage severity while achieving a target level of reliable service.
The optimization model aims at minimizing the costs of water supply-demand portfolios over the entire planning horizon: capital and construction costs, operation and maintenance costs, social costs, and environmental costs. A set of constraints needs to be met while optimizing the objective
Yina Liu Weakly sharp solutions and finite convergence of algorithms for a variational inequality problem The aim of the paper is to characterize weakly sharp solutions of a variational inequality problem. In particular, we present weak sharpness results by using primal and dual gap functions, and also without considering gap functions, either. The subdifferential and locally Lipschitz properties of a new gap function are first studied since they are useful for discussing weakly sharp solutions of the variational inequality. A result of finite termination of a class of algorithms for solving the variational inequality problem is also studied.
José Vicente-Pérez Zero duality gap for classes of DC optimization programs with polynomials In this talk we analyze some classes of difference of convex (DC) optimization programs involving polynomials. By way of generalizing the celebrated Farkas lemma to inequality systems involving the difference of a non-smooth convex function, defined by the maximum of convex polynomials over a compact convex set, and a convex polynomial, we show that there is no duality gap between this class of DC polynomial program and its associated conjugate dual problem. We then obtain strong duality under a constraint qualification. Finally we derive some particular cases and show applications.
Lorenzo Gentile, Gianluca Filippi, Edmondo Minisci, Massimiliano Vasile A hierarchical optimisation strategy for preliminary design of space systems The design of a space system is a complex task characterised by numerous interconnected disciplines and components. In the last years, researchers are developing tools for automating this challenging process. However, the problem presents a variety of features that makes traditional methods inefficient. In order to overcome these difficulties, we propose a new design methodology enhanced by the integration with an optimisation algorithm, the Structured-Chromosome GA. This copes with mixed-discrete global optimization problems with variable-size design space operating on a hierarchical problem.
Nikolaos Ploskas, Nikolaos Sahinidis, Nikolaos Samaras An advanced initialization procedure for the simplex algorithm This paper addresses the computation of an initial basis for the simplex algorithm for linear programming. We propose six algorithms for constructing an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates. Over a set of 62 large benchmarks, the best proposed algorithm produces remarkably sparse starting bases. Taking into account only the hard instances, the proposed algorithm results in 23% and 30% reduction of the geometric mean of the execution time of CPLEX’s primal and dual simplex algorithm, respectively.
Milan Hladik Approximation of the solution set of absolute value equations We consider the problem of solving absolute value equations, which is known to be equivalent to the linear complementarity problem. Despite an intensive research in the recent years, there are few results on approximating or bounding the solutions. We propose several outer approximations of the solution set. We present conditions for unsolvability and for existence of exponentially many solutions, too, and compare them with the known conditions. In some case the bounds are tight enough to determine the signs of the solution, and therefore also the solution itself.
Hector Ramirez Assessing fishery sustainable management and rebuilding plans under uncertainties through stochastic viability theory This talk discusses about the application of the stochastic viability theory to the management of natural resources. More specifically, we use this approach to propose and to assess exploitation strategies, as well as rebuilding plans, that permits a long-term sustainable fishery management. This methodology is applied to some Chilean fisheries.
Mercedes Pelegrin, Emilio Carrizosa, Alfredo Marín Clustering-embedded eigenvector centrality Identifying key members is one of the most important problems in social network analysis. Here, we combine eigenvector centrality with clustering to uncover the group of most relevant nodes, together with their spheres of influence. Modelling eigenvector computation over the clusters with decision variables involves highly non-linear equations, which have been linearized to produce a Mixed-Integer Linear formulation for the problem. We are able to find optimal solutions on networks of several hundreds of nodes and thousands of links, identifying community structures as a byproduct.
Sonia Cafieri, Pierre Hansen, Frédéric Messine Covering a rectangle with six circles: a Mathematical Programming approach We address the problem of covering a rectangle, considering various side lengths, with six identical circles. The objective is to minimize the radius of the circles while finding their position, in order to ensure that the rectangle is entirely covered. A conjecture is known in the literature on the different configurations of the circles (the way they are placed) to cover the rectangle, depending on its different side lengths. Starting from this conjecture, we provide nonlinear and mixed-integer nonlinear optimization models and find global optimal results for some previously open cases.
THI HONG VAN NGO, VAN NGOAN PHAM INDIRECT OPTIMAL ADAPTIVE CONTROL OF NONLINEAR SYSTEMS WITH PARAMETRIC UNCERTAINTIES This paper developed a method to transform the objective of adaptive control design for a general nonlinear system into an equivalent form of non-adaptive control objective for its modified system. This approach was used to solve the indirect optimal adaptive tracking control problem. This method has a great advantage to avoid the complexity in controller design. It was also shown that the solvability of the indirect optimal adaptive tracking problem for a given system is implied by the solvability of the Hamilton-Jacobi-Belman non-adaptive equation for its modified system.
Spyridon Pougkakiotis, Jacek Gondzio Interior Point-Proximal Method of Multipliers In this talk, we present a method (IP-PMM) that arises by combining Interior-Point Methods (IPMs) with Proximal Methods of Multiplyiers (PMMs). The resulting method, is a primal-dual regularized IPM. Computationally, it is well known that regularization significantly improves the robustness of IPMs. By slighlty altering the clasiccal theory of infeasible IPMs, we are able to prove (under very reasonable assumptions) that IP-PMM achieves polynomial complexity. We argue that regularization in the framework of IPMs, comes at almost no cost, yielding robust and efficient methods.
Zhen Shao, Coralia Cartis Jan Fiala Sketching for sparse linear least squares We discuss sketching techniques for sparse Linear Least Squares (LLS). We give theoretical bounds for the accuracy of the sketched solution/residual when hashing matrices are used for sketching, quantifying carefully the trade-off between the coherence of the original matrix and the sparsity of the hashing matrix. We use these to quantify the success of our algorithm that employs a sparse factorisation of the sketched matrix as a preconditioner for the original LLS before applying LSQR. We extensively compare our algorithm to state-of-the-art direct and iterative solvers for large sparse LLS.
Elif Garajová, Milan Hladik Solving Interval Linear Programs: From Theory to Algorithms Throughout the last years, several different approaches to optimization under uncertainty have emerged, including interval programming. An interval linear program represents a suitable model for practical optimization problems, in which only lower and upper bounds on the real data are known and it is assumed that the values can be perturbed independently within these bounds. In this talk, we will address one of the main questions of interval linear programming – the problem of describing (or at least tightly approximating) the set of optimal solutions over all possible scenarios.