Certifying convergence of Lasserre's hierarchy via flat truncation
From MaRDI portal
Publication:2434992
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.
In this paper, the author presents a new typical approach for solving the optimization of minimizing a polynomial optimization subject to polynomial constraints. The certificate for checking finite and asymptotical convergence of Lassees's hierarchy based on either Putinar's or Schmudgens's Positivstellensatz is established. The author also proves that flat truncation can be used as a certificate to check exactness of standard SOS relaxations and Jacobin SDP relaxations.
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
- A semidefinite approach for truncated \(K\)-moment problems
- Algebraic degree of polynomial optimization
- An exact Jacobian SDP relaxation for polynomial optimization
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Global optimization with polynomials and the problem of moments
- GloptiPoly 3: moments, optimization and semidefinite programming
- scientific article; zbMATH DE number 47995 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- Minimizing polynomials via sum of squares over the gradient ideal
- On the complexity of Putinar's Positivstellensatz
- Optimization of Polynomials on Compact Semialgebraic Sets
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Semidefinite representations for finite varieties
- Sums of squares of regular functions on real algebraic varieties
- Sums of squares, moment matrices and optimization over polynomials
- The K-moment problem for compact semi-algebraic sets
- Truncated \(K\)-moment problems in several variables
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(87)- Tensor eigenvalue complementarity problems
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Real eigenvalues of nonsymmetric tensors
- Tensor maximal correlation problems
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- A semidefinite relaxation method for second-order cone tensor eigenvalue complementarity problems
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- Tensor \(Z\)-eigenvalue complementarity problems
- Multi-objective convex polynomial optimization and semidefinite programming relaxations
- Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
- A global optimization method for multiple response optimization problems
- 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
- Local saddle points for unconstrained polynomial optimization
- Certifying the global optimality of quartic minimization over the sphere
- The saddle point problem of polynomials
- Hermitian completely positive matrices
- Completely positive tensors in the complex field
- A note on convex relaxations for the inverse eigenvalue problem
- On solving a class of fractional semi-infinite polynomial programming problems
- Tensor complementarity problems. II: Solution methods
- A semidefinite relaxation method for second-order cone polynomial complementarity problems
- SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection
- Higher-degree tensor eigenvalue complementarity problems
- Saddle points of rational functions
- Test of copositive tensors
- A semidefinite relaxation algorithm for checking completely positive separable matrices
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Minimizing trigonometric matrix polynomials over semi-algebraic sets
- A new approximation hierarchy for polynomial conic optimization
- Semidefinite relaxations for semi-infinite polynomial programming
- 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
- Positive maps and separable matrices
- Gposolver: a Matlab/C++ toolbox for global polynomial optimization
- Optimality conditions and finite convergence of Lasserre's hierarchy
- A complete semidefinite algorithm for detecting copositive matrices and tensors
- The \(\mathcal A\)-truncated \(K\)-moment problem
- A Lagrange multiplier expression method for bilevel polynomial optimization
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
- Stochastic polynomial optimization
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- Bilevel polynomial programs and semidefinite relaxation methods
- Generic properties for semialgebraic programs
- A semidefinite method for tensor complementarity problems
- Well-posedness in unconstrained polynomial optimization problems
- The maximum tensor complementarity eigenvalues
- Separability of Hermitian tensors and PSD decompositions
- Homogenization for polynomial optimization with unbounded sets
- Algebraic optimization of sequential decision problems
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Dehomogenization for completely positive tensors
- (Global) optimization: historical notes and recent developments
- Rational Generalized Nash Equilibrium Problems
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Hausdorff distance between convex semialgebraic sets
- A utopia point method-based robust vector polynomial optimization scheme
- On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials
- Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
- The moment-SOS hierarchy: applications and related topics
- Finite convergence of moment-SOS relaxations with nonreal radical ideals
- The multivariate eigenvalues of symmetric tensors
- Robust approximation of chance constrained optimization with polynomial perturbation
- A polynomial optimization framework for polynomial quasi-variational inequalities with moment-SOS relaxations
- A characterization for tightness of the sparse moment-SOS hierarchy
- Global optimization for the portfolio selection model with high-order moments
- Finite convergence of the moment-SOS hierarchy for polynomial matrix optimization
- Convergence rate for linear minimizer-estimators in the moment-sum-of-squares hierarchy
- Polynomial optimization relaxations for generalized semi-infinite programs
- Optimal transport-based distributionally robust optimization with polynomial uncertainty
- A global approach for generalized semi-infinite programs with polyhedral parameter sets
- Distributionally robust optimization with polynomial robust constraints
- A semidefinite relaxation method for linear and nonlinear complementarity problems with polynomials
- Polynomial optimization, certificates of positivity, and Christoffel function
- All saddle points for polynomial optimization
- Solving polynomial variational inequality problems via Lagrange multiplier expressions and moment-SOS relaxations
- Exact moment representation in polynomial optimization
- SPLD polynomial optimization and bounded degree SOS hierarchies
- Lagrange multiplier expressions for matrix polynomial optimization and tight relaxations
- Generalized Nash equilibrium problems with quasi-linear constraints
- A unified relaxation method for tensor split feasibility problems on unions of sets
- Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities
- Monotonically positive matrices
- Linear optimization with cones of moments and nonnegative polynomials
- Partially positive matrices
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)
