Strong duality in lasserre's hierarchy for polynomial optimization
From MaRDI portal
Publication:5963686
Abstract: A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set 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 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 . Our proof uses elementary results on SDP duality, and it does not assume that has an interior point.
Recommendations
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Convergence of Lasserre's hierarchy: the general case
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
- On duality gap with polynomial multipliers for polynomial optimization problems
Cites work
- scientific article; zbMATH DE number 1534291 (Why is no real title available?)
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Global optimization with polynomials and the problem of moments
- Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Optimisation globale et théorie des moments
- Optimization of Polynomials on Compact Semialgebraic Sets
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Strong duality conditions in semidefinite programming
Cited in
(32)- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- Simultaneous diagonalization via congruence of Hermitian matrices: some equivalent conditions and a numerical solution
- An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Generalized SOS-convexity and strong duality with SDP dual programs in polynomial optimization
- Convergence of Lasserre's hierarchy: the general case
- A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis
- Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches
- On solving a class of fractional semi-infinite polynomial programming problems
- Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
- Successive partial-symmetric rank-one algorithms for almost unitarily decomposable conjugate partial-symmetric tensors
- Lagrangian duality in convex conic programming with simple proofs
- An improved semidefinite programming hierarchy for testing entanglement
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- Lasserre hierarchy for large scale polynomial optimization in real and complex variables
- Role of redundant constraints for improving dual bounds in polynomial optimization problems
- Real ideal and the duality of semidefinite programming for polynomial optimization
- A hierarchy of spectral relaxations for polynomial optimization
- A survey on conic relaxations of optimal power flow problem
- Approximation algorithms for optimization of real-valued general conjugate complex forms
- On duality gap with polynomial multipliers for polynomial optimization problems
- A unified framework of SAGE and SONC polynomials and its duality theory
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- On the effective Putinar's Positivstellensatz and moment approximation
- Computing the Hausdorff boundary measure of semialgebraic sets
- On decompositions and approximations of conjugate partial-symmetric tensors
- Exploiting sparsity for semi-algebraic set volume computation
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- SOS is not obviously automatizable, even approximately
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- The constant trace property in noncommutative optimization
This page was built for publication: Strong duality in lasserre's hierarchy for polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963686)
