Strong duality in lasserre's hierarchy for polynomial optimization
From MaRDI portal
Publication:5963686
DOI10.1007/S11590-015-0868-5zbMATH Open1339.90267arXiv1405.7334OpenAlexW2051634716MaRDI QIDQ5963686FDOQ5963686
Publication date: 23 February 2016
Published in: Optimization Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1405.7334
Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Global optimization with polynomials and the problem of moments
- Optimization of Polynomials on Compact Semialgebraic Sets
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Optimisation globale et théorie des moments
- Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions
Cited In (30)
- Approximation algorithms for optimization of real-valued general conjugate complex forms
- On solving a class of fractional semi-infinite polynomial programming problems
- 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
- Computing the Hausdorff Boundary Measure of Semialgebraic Sets
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- On duality gap with polynomial multipliers for polynomial optimization problems
- SOS Is Not Obviously Automatizable, Even Approximately
- Successive partial-symmetric rank-one algorithms for almost unitarily decomposable conjugate partial-symmetric tensors
- Role of redundant constraints for improving dual bounds in polynomial optimization problems
- A survey on conic relaxations of optimal power flow problem
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- A hierarchy of spectral relaxations for polynomial optimization
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- Simultaneous Diagonalization via Congruence of Hermitian Matrices: Some Equivalent Conditions and a Numerical Solution
- Lagrangian duality in convex conic programming with simple proofs
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- An improved semidefinite programming hierarchy for testing entanglement
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
- The constant trace property in noncommutative optimization
- Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches
- On the effective Putinar's Positivstellensatz and moment approximation
- Exploiting sparsity for semi-algebraic set volume computation
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
- A unified framework of SAGE and SONC polynomials and its duality theory
Uses Software
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)
