Positivity certificates and polynomial optimization on non-compact semialgebraic sets

DOI10.1007/S10107-021-01634-1zbMATH Open1494.90073arXiv1911.11428OpenAlexW3133708012MaRDI QIDQ2149557FDOQ2149557

Victor Magron, Jean B. Lasserre, Ngoc Hoang Anh Mai

Publication date: 29 June 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu [Comptes Rendus de l'Acad'emie des Sciences-Series I-Mathematics, 328(6) (1999) pp. 495-499]. We use Jacobi's technique from [Mathematische Zeitschrift, 237(2) (2001) pp. 259-273] to provide an alternative proof with an effective degree bound on the sums of squares multipliers in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization problem. Convergence of this hierarchy to a neighborhood of the optimal value as well as strong duality and analysis are guaranteed. In a second contribution, we introduce a new numerical method for solving systems of polynomial inequalities and equalities with possibly uncountably many solutions. As a bonus, one may apply this method to obtain approximate global optimizers in polynomial optimization.

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

Recommendations

• On the complexity of Putinar-Vasilescu's Positivstellensatz
• On polynomial optimization over non-compact semi-algebraic sets
• On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
• A bounded degree SOS hierarchy for polynomial optimization
• Optimization of Polynomials on Compact Semialgebraic Sets

zbMATH Keywords

polynomial optimizationsemidefinite programmingsums of squarespolynomial systemsnonnegativity certificatemoment-SOS hierarchybasic semialgebraic setPutinar's positivstellensatzuniform denominators

Mathematics Subject Classification ID

Semidefinite programming (90C22) Numerical computation of roots of polynomial equations (65H04) Polynomial optimization (90C23)

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
• The \(K\)-moment problem for compact semi-algebraic sets
• Uniform denominators in Hilbert's seventeenth problem
• On an extension of Pólya's Positivstellensatz
• Minimizing polynomials via sum of squares over the gradient ideal
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Sums of squares, moment matrices and optimization over polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the absence of uniform denominators in Hilbert’s 17th problem
• Strong duality conditions in semidefinite programming
• A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure
• Representations of Positive Polynomials and Optimization on Noncompact Semialgebraic Sets
• Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
• Discriminants and nonnegative polynomials
• On the complexity of Putinar's Positivstellensatz
• Semidefinite characterization and computation of zero-dimensional real radical ideals
• A Sum of Squares Approximation of Nonnegative Polynomials
• Revisiting two theorems of Curto and Fialkow on moment matrices
• Anneaux preordonnes
• Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
• Optimality conditions and finite convergence of Lasserre's hierarchy
• On polynomial optimization over non-compact semi-algebraic sets
• Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
• Positive polynomials on semi-algebraic sets
• Truncated \(K\)-moment problems in several variables
• An Introduction to Polynomial and Semi-Algebraic Optimization
• Sums of squares on the hypercube
• An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem
• Continous, piecewise-polynomial functions which solve Hilbert's 17th problem.
• A representation theorem for certain partially ordered commutative rings
• There are significantly more nonnegative polynomials than sums of squares
• Title not available (Why is that?)
• Semidefinite Approximations for Global Unconstrained Polynomial Optimization
• SOS approximations of nonnegative polynomials via simple high degree perturbations
• Solving moment problems by dimensional extension
• Strong duality in lasserre's hierarchy for polynomial optimization
• Polynomials in \(\mathbb{R}[x,y]\) that are sums of squares in \(\mathbb{R}(x,y)\)
• Approximating Positive Polynomials Using Sums of Squares
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions
• A Positivstellensatz for projective real varieties
• Iterated rings of bounded elements and generalizations of Schmüdgens Positivstellensatz
• Coercive Polynomials and Their Newton Polytopes
• In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
• On Exact Polya and Putinar's Representations
• A paradox in bosonic energy computations via semidefinite programming relaxations
• Sharp degree bounds for sum-of-squares certificates on projective curves
• The IMO compendium. A collection of problems suggested for the International Mathematical Olympiads: 1959--2009

Cited In (5)

• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• Homogenization for polynomial optimization with unbounded sets
• Finite convergence of moment-SOS relaxations with nonreal radical ideals
• Certifying Polynomial Nonnegativity via Hyperbolic Optimization
• On the effective Putinar's Positivstellensatz and moment approximation

Uses Software

• SparsePOP
• GloptiPoly

This page was built for publication: Positivity certificates and polynomial optimization on non-compact semialgebraic sets

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