Global Optimization

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , , ,

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more

    EFIX: Exact Fixed Point Methods for Distributed Optimization

  • Dušan Jakovetić
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Convex Optimization, Global Optimization Theory, Quadratic Programming Tags , , ,

    We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation – transforming the original problem into a constrained problem in a higher dimensional space – to define a sequence of suitable quadratic penalty subproblems with increasing penalty … Read more

    Homogeneous polynomials and spurious local minima on the unit sphere

  • Jean-Bernard Lasserre
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory

    We consider forms on the Euclidean unit sphere. We obtain obtain a simple and complete characterization of all points that satisfies the standard second-order necessary condition of optimality. It is stated solely in terms of the value of (i) f, (ii) the norm of its gradient, and (iii) the first two smallest eigenvalues of its … Read more

    The Moment-SOS hierarchy and the Christoffel-Darboux kernel

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Other Topics

    We consider the global minimization of a polynomial on a compact set B. We show that each step of the Moment-SOS hierarchy has a nice and simple interpretation that complements the usual one. Namely, it computes coefficients of a polynomial in an orthonormal basis of $L^2(B,\mu)$ where $\mu$ is an arbitrary reference measure whose support … Read more

    Compact mixed-integer programming relaxations in quadratic optimization

  • Ben Beach
  • Robert Hildebrand
  • Joey Huchette
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization

    We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in … Read more

    A Geometric View of SDP Exactness in QCQPs and its Applications

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

    Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest … Read more

    Complexity, Exactness, and Rationality in Polynomial Optimization

  • Daniel Bienstock
  • Alberto Del Pia
  • Robert Hildebrand
    • Categories Global Optimization Theory, Nonlinear Optimization Tags , ,

    We study representation of solutions and certificates to quadratic and cubic optimization problems. Specifically, we focus on minimizing a cubic function over a polyhedron and also minimizing a linear function over quadratic constraints. We show when there exist rational feasible solutions (and if we can detect them) and when we can prove feasibility of sublevel … Read more

    Constrained stochastic blackbox optimization using a progressive barrier and probabilistic estimates

  • Kwassi Joseph Dzahini
  • Michael Kokkolaras
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Approaches Tags , , ,

    This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose … Read more

    A Reformulation-Linearization Technique for Optimization over Simplices

  • Aras Selvi
  • Dick den Hertog
  • Wolfram Wiesemann
    • Categories Constrained Nonlinear Optimization, Global Optimization, Global Optimization Theory Tags , ,

    We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more