Global Optimization

Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization

  • Shixuan Zhang
  • Xu Andy Sun
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Stochastic Programming Tags , , ,

    In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{non-Lipschitz-continuous} value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient … Read more

    On tackling reverse convex constraints for non-overlapping of unequal circles

  • Chrysanthos E. Gounaris
  • Akang Wang
    • Categories Global Optimization, Global Optimization Applications Tags , , , , ,

    We study the unequal circle-circle non-overlapping constraints, a form of reverse convex constraints that often arise in optimization models for cutting and packing applications. The feasible region induced by the intersection of circle-circle non-overlapping constraints is highly non-convex, and standard approaches to construct convex relaxations for spatial branch-and-bound global optimization of such models typically yield … Read more

    Proximity measures based on KKT points for constrained multi-objective optimization

  • Gabriele Eichfelder
  • Leo Warnow
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Multi-Criteria Optimization Tags , ,

    An important aspect of optimization algorithms, for instance evolutionary algorithms, are termination criteria that measure the proximity of the found solution to the optimal solution set. A frequently used approach is the numerical verification of necessary optimality conditions such as the Karush-Kuhn-Tucker (KKT) conditions. In this paper, we present a proximity measure which characterizes the … Read more

    The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment

  • Jonas Egerer
  • Veronika Grimm
  • Thomas Kleinert
  • Martin Schmidt
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both … Read more

    On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

  • Maxime Gasse
  • Ambros Gleixner
  • Andrea Lodi
  • Felipe Serrano
  • Benjamin Müller
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags ,

    The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens … Read more

    The extreme rays of the \times6$ copositive cone

  • Andrei Afonin
  • Peter J.C. Dickinson
  • Roland Hildebrand
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , ,

    We provide a complete classification of the extreme rays of the $6 \times 6$ copositive cone ${\cal COP}^6$. We proceed via a coarse intermediate classification of the possible minimal zero support set of an exceptional extremal matrix $A \in {\cal COP}^6$. To each such minimal zero support set we construct a stratified semi-algebraic manifold in … Read more

    On the tightness of SDP relaxations of QCQPs

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show … Read more

    Multi-objective Optimization Based Algorithms for Solving Mixed Integer Linear Minimum Multiplicative Programs

  • Hadi Charkhgard
  • Vahid Mahmoodian
  • Yu Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization

    We present two new algorithms for a class of single-objective non-linear optimization problems, the so-called Mixed Integer Linear minimum Multiplicative Programs (MIL-mMPs). This class of optimization problems has a desirable characteristic: a MIL-mMP can be viewed as a special case of the problem of optimization over the efficient set in multi-objective optimization. The proposed algorithms … Read more

    Optimization and Validation of Pumping System Design and Operation for Water Supply in High-Rise Buildings

  • Lena C. Altherr
  • Peter F. Pelz
  • Philipp Leise
  • Imke-Sophie Lorenz
  • Tim M. Müller
    • Categories Global Optimization Applications, Mechanical Engineering Tags , , , , ,

    The application of mathematical optimization methods provides the capacity to increase the energy efficiency and to lower the investment costs of technical systems, considerably. We present a system approach for the optimization of the design and operation of pumping systems and exemplify it by applying it to the water supply of high-rise buildings. The underlying … Read more

    Spurious Local Minima Exist for Almost All Over-parameterized Neural Networks

  • Tian Ding
  • Ruoyu Sun
  • Dawei Li
    • Categories Global Optimization Theory, Nonlinear Optimization

    A popular belief for explaining the efficiency in training deep neural networks is that over-paramenterized neural networks have nice landscape. However, it still remains unclear whether over-parameterized neural networks contain spurious local minima in general, since all current positive results cannot prove non-existence of bad local minima, and all current negative results have strong restrictions … Read more