Strong duality in Lasserre's hierarchy for polynomial optimization
Not on the map. Why?
Abstract (arXiv)
A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set K described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J.~B.~Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, when the POP feasibility set K is compact, we show that there is no duality gap between each primal and dual SDP problem in Lasserre's hierarchy, provided a redundant ball constraint is added to the description of set K. Our proof uses elementary results on SDP duality, and it does not assume that K has an interior point.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 May 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 0; 2023: 0; 2024: 1.
3 papers.
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2021An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimizationcited by 10
- 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
- 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications28 Oct 2024
- 2021Private Robust Estimation by Stabilizing Convex Relaxations7 Dec 2021
- 2021An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization28 May 2021