On polynomial optimization over non-compact semi-algebraic sets

DOI10.1007/S10957-014-0545-3zbMATH Open1302.90208DBLPjournals/jota/JeyakumarLL14arXiv1304.4552OpenAlexW2037887312WikidataQ59241486 ScholiaQ59241486MaRDI QIDQ481041FDOQ481041

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)

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.

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

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

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)

Cites Work

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

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
• Homogenization for polynomial optimization with unbounded sets
• Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible 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
• Convergences for robust bilevel polynomial programmes with applications
• Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method
• A convergent hierarchy of SDP relaxations for a class of hard robust global polynomial optimization problems
• 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

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)