polynomial optimization

Solving sparse polynomial optimization problems with chordal structure using the sparse, bounded-degree sum-of-squares hierarchy

  • Joachim Dahl
  • Etienne de Klerk
  • Ahmadreza Marandi
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser, Lasserre and Toh [arXiv:1607.01151,2016] constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proven by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality … Read more

    Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Roxana Hess
    • Categories Semi-definite Programming Tags , , , , ,

    We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more

    Solving rank-constrained semidefinite programs in exact arithmetic

  • Simone Naldi
    • Categories Semi-definite Programming Tags , , , , , , , ,

    We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in … Read more

    DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure … Read more

    On the convergence rate of grid search for polynomial optimization over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
  • Juan C. Vera
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags ,

    We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator ${r} \in \mathbb{N}$. It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric … Read more

    Bound-constrained polynomial optimization using only elementary calculations

  • Etienne de Klerk
  • Jean-Bernard Lasserre
  • Monique Laurent
  • Zhao Sun
    • Categories Bound-constrained Optimization, Global Optimization Theory Tags , ,

    We provide a monotone non increasing sequence of upper bounds $f^H_k$ ($k\ge 1$) converging to the global minimum of a polynomial $f$ on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Polynomial Root Radius Optimization with Affine Constraints

  • Julia Eaton
  • Sara Grundel
  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Other Topics Tags , ,

    The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree $n$, with either real or complex coefficients, subject to $k$ consistent affine constraints on the coefficients. We show that there always exists an optimal … Read more

    Copositivity for second-order optimality conditions in general smooth optimization problems

  • Immanuel M. Bomze
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , , ,

    Second-order local optimality conditions involving copositivity of the Hessian of the Lagrangian on the reduced linearization cone have the advantage that there is only a small gap between sufficient (the Hessian is strictly copositive) and necessary (the Hessian is copositive) conditions. In this respect, this is a proper generalization of convexity of the Lagrangian. We … Read more

    Coercive polynomials and their Newton polytopes

  • Tomas Bajbar
  • Oliver Stein
    • Categories Global Optimization Theory, Polyhedra Tags , , ,

    Many interesting properties of polynomials are closely related to the geometry of their Newton polytopes. In this article we analyze the coercivity on $\mathbb{R}^n$ of multivariate polynomials $f\in \mathbb{R}[x]$ in terms of their Newton polytopes. In fact, we introduce the broad class of so-called gem regular polynomials and characterize their coercivity via conditions imposed on … Read more