polynomial optimization

Density, Determinacy, Duality and a Regularized Moment-SOS Hierarchy

  • Didier Henrion
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    The standard moment-sum-of-squares (SOS) hierarchy is a powerful method for solving global polynomial optimization problems. However, its convergence relies on Putinar’s Positivstellensatz, which requires the feasible set to satisfy the algebraic Archimedean property. In this paper, we introduce a regularized moment-SOS hierarchy capable of handling problems on unbounded sets or bounded sets violating the Archimedean … Read more

    A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal

  • Jie Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , , , , , ,

    This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain … Read more

    Moment-sos and spectral hierarchies for polynomial optimization on the sphere and quantum de Finetti theorems

  • Alexander Taveira Blomenhofer
  • Monique Laurent
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We revisit the convergence analysis of two approximation hierarchies for polynomial optimization on the unit sphere. The first one is based on the moment-sos approach and gives semidefinite bounds for which Fang and Fawzi (2021) showed an analysis in \(O(1/r^2)\) for the r-th level bound, using the polynomial kernel method. The second hierarchy was recently … Read more

    Dual certificates of primal cone membership

  • Joonyeob Lee
  • Dávid Papp
  • Anita Varga
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , ,

    We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more

    Solving unbounded optimal control problems with the moment-SOS hierarchy

  • Karolina Sehnalova
  • Didier Henrion
  • Milan Korda
  • Martin Kružík
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    The behaviour of the moment-sums-of-squares (moment-SOS) hierarchy for polynomial optimal control problems on compact sets has been explored to a large extent. Our contribution focuses on the case of non-compact control sets. We describe a new approach to optimal control problems with unbounded controls, using compactification by partial homogenization, leading to an equivalent infinite dimensional … Read more

    Granularity for mixed-integer polynomial optimization problems

  • Carl Eggen
  • Oliver Stein
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    Finding good feasible points is crucial in mixed-integer programming. For this purpose we combine a sufficient condition for consistency, called granularity, with the moment-/sos-hierarchy from polynomial optimization. If the mixed-integer problem is granular, we obtain feasible points by solving continuous polynomial problems and rounding their optimal points. The moment-/sos-hierarchy is hereby used to solve those … Read more

    Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

  • Didier Henrion
  • Adrien Le Franc
  • Victor Magron
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We describe a parametric univariate quadratic optimization problem for which the moment-SOS hierarchy has finite but increasingly slow convergence when the parameter tends to its limit value. We estimate the order of finite convergence as a function of the parameter. ArticleDownload View PDF

    Refined TSSOS

  • Daria Shaydurova
  • Volker Kaibel
  • Sebastian Sager
    • Categories Global Optimization Applications, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency … Read more

    Sparse Polynomial Optimization with Unbounded Sets

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    This paper considers sparse polynomial optimization with unbounded sets. When the problem possesses correlative sparsity, we propose a sparse homogenized Moment-SOS hierarchy with perturbations to solve it. The new hierarchy introduces one extra auxiliary variable for each variable clique according to the correlative sparsity pattern. Under the running intersection property, we prove that this hierarchy … Read more

    Solving moment and polynomial optimization problems on Sobolev spaces

  • Didier Henrion
  • Alessandro Rudi
    • Categories Global Optimization, Infinite Dimensional Optimization, Semi-definite Programming Tags , , ,

    Using standard tools of harmonic analysis, we state and solve the problem of moments for positive measures supported on the unit ball of a Sobolev space of multivariate periodic trigonometric functions. We describe outer and inner semidefinite approximations of the cone of Sobolev moments. They are the basic components of an infinite-dimensional moment-sums of squares … Read more