Strong duality in lasserre's hierarchy for polynomial optimization
From MaRDI portal
(Redirected from 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
(37)- A unified framework of SAGE and SONC polynomials and its duality theory
- Simultaneous diagonalization via congruence of Hermitian matrices: some equivalent conditions and a numerical solution
- Approximation algorithms for optimization of real-valued general conjugate complex forms
- On solving a class of fractional semi-infinite polynomial programming problems
- Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
- Convergence of Lasserre's hierarchy: the general case
- On decompositions and approximations of conjugate partial-symmetric tensors
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- Lasserre hierarchy for large scale polynomial optimization in real and complex variables
- On duality gap with polynomial multipliers for polynomial optimization problems
- Role of redundant constraints for improving dual bounds in polynomial optimization problems
- Successive partial-symmetric rank-one algorithms for almost unitarily decomposable conjugate partial-symmetric tensors
- A survey on conic relaxations of optimal power flow problem
- Exact moment representation in polynomial optimization
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
- A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- Geometry of exactness of moment-SOS relaxations for polynomial optimization
- A hierarchy of spectral relaxations for polynomial optimization
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- Sum-of-squares hierarchy for the Gromov-Wasserstein problem
- Convergence rates of sum-of-squares hierarchies for polynomial semidefinite programs
- Lagrangian duality in convex conic programming with simple proofs
- Real ideal and the duality of semidefinite programming for polynomial optimization
- Computing the Hausdorff boundary measure of semialgebraic sets
- An improved semidefinite programming hierarchy for testing entanglement
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- SOS is not obviously automatizable, even approximately
- Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches
- The constant trace property in noncommutative optimization
- Exploiting sparsity for semi-algebraic set volume computation
- On the effective Putinar's Positivstellensatz and moment approximation
- Generalized SOS-convexity and strong duality with SDP dual programs in polynomial optimization
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
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)
