Certifying convergence of Lasserre's hierarchy via flat truncation
From MaRDI portal
Publication:2434992
DOI10.1007/S10107-012-0589-9zbMATH Open1305.65151arXiv1106.2384OpenAlexW2052557161MaRDI QIDQ2434992FDOQ2434992
Authors: Jiawang Nie 
Publication date: 3 February 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: This paper studies how to certify the convergence of Lasserre's hierarchy of semidefinite programming relaxations for solving multivariate polynomial optimization. We propose flat truncation as a general certificate for this purpose. Assume the set of global minimizers is nonempty and finite. Our main results are: i) Putinar type Lasserre's hierarchy has finite convergence if and only if flat truncation holds, under some general assumptions, and this is also true for the Schmudgen type one; ii) under the archimedean condition, flat truncation is asymptotically satisfied for Putinar type Lasserre's hierarchy, and similar is true for the Schmudgen type one; iii) for the hierarchy of Jacobian SDP relaxations, flat truncation is always satisfied. The case of unconstrained polynomial optimization is also discussed.
Full work available at URL: https://arxiv.org/abs/1106.2384
Recommendations
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
- A bounded degree SOS hierarchy for polynomial optimization
- Convergence of Lasserre's hierarchy: the general case
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- 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?)
- The \(K\)-moment problem for compact semi-algebraic sets
- Minimizing polynomials via sum of squares over the gradient ideal
- GloptiPoly 3: moments, optimization and semidefinite programming
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Optimization of Polynomials on Compact Semialgebraic Sets
- Semidefinite representations for finite varieties
- On the complexity of Putinar's Positivstellensatz
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- An exact Jacobian SDP relaxation for polynomial optimization
- Title not available (Why is that?)
- A semidefinite approach for truncated \(K\)-moment problems
- Algebraic degree of polynomial optimization
- Truncated \(K\)-moment problems in several variables
- Sums of squares of regular functions on real algebraic varieties
Cited In (69)
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Separability of Hermitian tensors and PSD decompositions
- The saddle point problem of polynomials
- The maximum tensor complementarity eigenvalues
- 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
- Higher-degree tensor eigenvalue complementarity problems
- Tensor complementarity problems. II: Solution methods
- Distributionally robust optimization with moment ambiguity sets
- An SDP relaxation method for Perron pairs of a nonnegative tensor
- Convergence of Lasserre's hierarchy: the general case
- A note on convex relaxations for the inverse eigenvalue problem
- A complete semidefinite algorithm for detecting copositive matrices and tensors
- Tensor eigenvalue complementarity problems
- Local saddle points for unconstrained polynomial optimization
- A global optimization method for multiple response optimization problems
- Minimizing trigonometric matrix polynomials over semi-algebraic sets
- Saddle points of rational functions
- Real eigenvalues of nonsymmetric tensors
- Tensor maximal correlation problems
- Optimality conditions and finite convergence of Lasserre's hierarchy
- A semidefinite relaxation algorithm for checking completely positive separable matrices
- Test of copositive tensors
- A semidefinite relaxation method for second-order cone tensor eigenvalue complementarity problems
- Multi-objective convex polynomial optimization and semidefinite programming relaxations
- Gposolver: a Matlab/C++ toolbox for global polynomial optimization
- Tensor \(Z\)-eigenvalue complementarity problems
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- The \(\mathcal A\)-truncated \(K\)-moment problem
- Linear optimization with cones of moments and nonnegative polynomials
- Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities
- Monotonically positive matrices
- Certifying the global optimality of quartic minimization over the sphere
- Partially positive matrices
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Well-posedness in unconstrained polynomial optimization problems
- Generic properties for semialgebraic programs
- Hermitian completely positive matrices
- Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
- A Lagrange multiplier expression method for bilevel polynomial optimization
- Positive maps and separable matrices
- A semidefinite relaxation method for second-order cone polynomial complementarity problems
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- Bilevel polynomial programs and semidefinite relaxation methods
- A new approximation hierarchy for polynomial conic optimization
- Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints
- Quadratic tensor eigenvalue complementarity problems
- Convex generalized Nash equilibrium problems and polynomial optimization
- Completely positive tensors in the complex field
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Semidefinite relaxations for semi-infinite polynomial programming
- SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
- A semidefinite method for tensor complementarity problems
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Dehomogenization for completely positive tensors
- Rational Generalized Nash Equilibrium Problems
- A utopia point method-based robust vector polynomial optimization scheme
- Hausdorff distance between convex semialgebraic sets
- Homogenization for polynomial optimization with unbounded sets
- The moment-SOS hierarchy: applications and related topics
- Algebraic optimization of sequential decision problems
- Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
- Finite convergence of moment-SOS relaxations with nonreal radical ideals
- On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials
- Robust approximation of chance constrained optimization with polynomial perturbation
- The multivariate eigenvalues of symmetric tensors
- (Global) optimization: historical notes and recent developments
Uses Software
This page was built for publication: Certifying convergence of Lasserre's hierarchy via flat truncation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434992)
