On polynomial optimization over non-compact semi-algebraic sets

DOI10.1007/S10957-014-0545-3MaRDI QIDQ481041zbMATH OpenOpenAlexDBLPWikidataFDO

Authors V. Jeyakumar, Jean B. Lasserre, G. Li

Publication date 12 December 2014

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4552

zbMATH Keywords

polynomial optimizationsemidefinite programming relaxationsnon-compact semi-algebraic setspositivstellensatzë

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Semialgebraic sets and related spaces (14P10)

Abstract: We consider the class of polynomial optimization problems $inff(x):xinK$ for which the quadratic module generated by the polynomials that define $K$ and the polynomial $c-f$ (for some scalar $c$) is Archimedean. For such problems, the optimal value can be approximated as closely as desired by solving a hierarchy of semidefinite programs and the convergence is finite generically. Moreover, the Archimedean condition (as well as a sufficient coercivity condition) can also be checked numerically by solving a similar hierarchy of semidefinite programs. In other words, under reasonable assumptions the now standard hierarchy of SDP-relaxations extends to the non-compact case via a suitable modification.

Recommendations

• Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• Representations of positive polynomials and optimization on noncompact semialgebraic sets
• A bounded degree SOS hierarchy for polynomial optimization
• Optimization of Polynomials on Compact Semialgebraic Sets

Cites work

• Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
• Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
• Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
• Global minimization of a multivariate polynomial using matrix methods
• Global optimization with polynomials and the problem of moments
• Minimizing polynomials via sum of squares over the gradient ideal
• On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Pre- and Post-Processing Sum-of-Squares Programs in Practice
• Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
• Semidefinite Approximations for Global Unconstrained Polynomial Optimization
• Sums of squares on real algebraic curves
• Sums of squares, moment matrices and optimization over polynomials
• The K-moment problem for compact semi-algebraic sets

Cited in

(26)

• On the existence of Pareto solutions for polynomial vector optimization problems
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• Tangencies and polynomial optimization
• Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
• Homogenization for polynomial optimization with unbounded sets
• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• A semidefinite relaxation algorithm for checking completely positive separable matrices
• Tight SDP relaxations for a class of robust SOS-convex polynomial programs without the Slater condition
• On duality gap with polynomial multipliers for polynomial optimization problems
• Coercive polynomials: stability, order of growth, and Newton polytopes
• Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems
• Steklov convexification and a trajectory method for global optimization of multivariate quartic polynomials
• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• A bilevel Farkas lemma to characterizing global solutions of a class of bilevel polynomial programs
• Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
• Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints
• Optimizing a linear function over a noncompact real algebraic variety
• A convergent hierarchy of SDP relaxations for a class of hard robust global polynomial optimization problems
• Convergences for robust bilevel polynomial programmes with applications
• Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method
• Polynomial optimization on some unbounded closed semi-algebraic sets
• Optimization problems over noncompact semialgebraic sets
• On the complexity of testing attainment of the optimal value in nonlinear optimization
• Exact conic programming relaxations for a class of convex polynomial cone programs
• Generating valid linear inequalities for nonlinear programs via sums of squares
• Coercive Polynomials and Their Newton Polytopes

Describes a project that uses

Uses Software

• YALMIP

This page was built for publication: On polynomial optimization over non-compact semi-algebraic sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q481041)