Optimality conditions and finite convergence of Lasserre's hierarchy
From MaRDI portal
Publication:403636
DOI10.1007/S10107-013-0680-XzbMATH Open1300.65041arXiv1206.0319OpenAlexW1964603869MaRDI QIDQ403636FDOQ403636
Authors: Jiawang Nie 
Publication date: 29 August 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: Lasserre's hierarchy is a sequence of semidefinite relaxations for solving polynomial optimization problems globally. This paper studies the relationship between optimality conditions in nonlinear programming theory and finite convergence of Lasserre's hierarchy. Our main results are: i) Lasserre's hierarchy has finite convergence when the constraint qualification, strict complementarity and second order sufficiency conditions hold at every global minimizer, under the standard archimedean assumption; the proof uses a result of Marshall on boundary hessian conditions. ii) these optimality conditions are all satisfied at every local minimizer if a finite set of polynomials, which are in the coefficients of input polynomials, do not vanish at the input data (i.e., they hold in a Zariski open set). This implies that Lasserre's hierarchy has finite convergence generically.
Full work available at URL: https://arxiv.org/abs/1206.0319
Recommendations
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Convergence of Lasserre's hierarchy: the general case
- Polynomial optimization with real varieties
polynomial optimizationoptimality conditionssum of squaresfinite convergencesemidefinite programLasserre's hierarchy
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- GloptiPoly
- GloptiPoly 3: moments, optimization and semidefinite programming
- Sums of squares, moment matrices and optimization over polynomials
- Positivity and sums of squares: a guide to recent results
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Semidefinite representations for finite varieties
- Discriminants and nonnegative polynomials
- An exact Jacobian SDP relaxation for polynomial optimization
- Positive polynomials and sums of squares
- Distinguished representations of non-negative polynomials
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- Algebraic degree of polynomial optimization
- Sums of squares of regular functions on real algebraic varieties
- Representations of non-negative polynomials having finitely many zeros
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Non-existence of degree bounds for weighted sums of squares representations
- Polynomial optimization with real varieties
Cited In (only showing first 100 items - show all)
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- The saddle point problem of polynomials
- Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools
- Strong duality in lasserre's hierarchy for polynomial optimization
- Stochastic polynomial optimization
- On solving a class of fractional semi-infinite polynomial programming problems
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- Computing lower rank approximations of matrix polynomials
- Distributionally robust optimization with moment ambiguity sets
- LP Formulations for Polynomial Optimization Problems
- Qualification Conditions in Semialgebraic Programming
- A multilevel analysis of the Lasserre hierarchy
- Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
- Convergence of Lasserre's hierarchy: the general case
- Tensor eigenvalue complementarity problems
- Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph
- Robust SOS-convex polynomial optimization problems: exact SDP relaxations
- Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
- Stability and genericity for semi-algebraic compact programs
- Saddle points of rational functions
- Generic Properties for Semialgebraic Programs
- Real eigenvalues of nonsymmetric tensors
- Tensor maximal correlation problems
- A semidefinite relaxation algorithm for checking completely positive separable matrices
- Real Radicals and Finite Convergence of Polynomial Optimization Problems
- On polynomial optimization over non-compact semi-algebraic sets
- Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm
- Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
- Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP
- A survey on conic relaxations of optimal power flow problem
- Well-Posedness in Unconstrained Polynomial Optimization Problems
- Computing the distance between the linear matrix pencil and the completely positive cone
- Completely positive tensor recovery with minimal nuclear value
- Set-membership errors-in-variables identification of MIMO linear systems
- Tensor \(Z\)-eigenvalue complementarity problems
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- The \(\mathcal A\)-truncated \(K\)-moment problem
- Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography
- Best Nonnegative Rank-One Approximations of Tensors
- Symmetric Tensor Nuclear Norms
- Bilevel Polynomial Programs and Semidefinite Relaxation Methods
- A new algorithm for concave quadratic programming
- Linear optimization with cones of moments and nonnegative polynomials
- Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities
- Monotonically positive matrices
- Interiors of completely positive cones
- Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
- An effective version of Schmüdgen's Positivstellensatz for the hypercube
- Partially positive matrices
- A hierarchy of spectral relaxations for polynomial optimization
- The moment-SOS hierarchy and the Christoffel-Darboux kernel
- On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
- Hermitian completely positive matrices
- A bounded degree SOS hierarchy for polynomial optimization
- Positive maps and separable matrices
- Exact algorithms for linear matrix inequalities
- A sublevel moment-SOS hierarchy for polynomial optimization
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- A new approximation hierarchy for polynomial conic optimization
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Convergence of an SDP hierarchy and optimality of robust convex polynomial optimization problems
- A unified framework for the identification of a general class of multivariable nonlinear block‐structured systems
- Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
- On the complexity of testing attainment of the optimal value in nonlinear optimization
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Semidefinite relaxations for semi-infinite polynomial programming
- New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
- On the complexity of Putinar-Vasilescu's Positivstellensatz
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- Separability of Hermitian tensors and PSD decompositions
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Dehomogenization for completely positive tensors
- Global minimization of polynomial integral functionals
- Title not available (Why is that?)
- A note on convex relaxations for the inverse eigenvalue problem
- On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
- A utopia point method-based robust vector polynomial optimization scheme
- Solving rank-constrained semidefinite programs in exact arithmetic
- Generalized truncated moment problems with unbounded sets
- Homogenization for polynomial optimization with unbounded sets
- A Lagrange Multiplier Expression Method for Bilevel Polynomial Optimization
- Homogeneous polynomials and spurious local minima on the unit sphere
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- The moment-SOS hierarchy: applications and related topics
- Algebraic optimization of sequential decision problems
- Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Invariants of SDP exactness in quadratic programming
- Sum-of-squares certificates for copositivity via test states
- Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
- Finite convergence of moment-SOS relaxations with nonreal radical ideals
- Towards global solutions for nonconvex two-stage stochastic programs: a polynomial lower approximation approach
- On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials
- Certifying the global optimality of quartic minimization over the sphere
- A hierarchy of semidefinite relaxations for completely positive tensor optimization problems
- On continuous selections of polynomial functions
- Robust approximation of chance constrained optimization with polynomial perturbation
- Second Order Conditions to Decompose Smooth Functions as Sums of Squares
Uses Software
This page was built for publication: Optimality conditions and finite convergence of Lasserre's hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403636)
