On the complexity of Putinar's Positivstellensatz

DOI10.1016/j.jco.2006.07.002zbMath1143.13028arXiv0812.2657OpenAlexW2083449425MaRDI QIDQ870344

Markus Schweighofer, Jia-Wang Nie

Publication date: 12 March 2007

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

complexitymoment problempositive polynomialsum of squaresquadratic moduleoptimization of polynomials

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Semidefinite programming (90C22) Sums of squares and representations by other particular quadratic forms (11E25) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)

Related Items (67)

Łojasiewicz inequalities with explicit exponents for smallest singular value functions ⋮ Some applications of polynomial optimization in operations research and real-time decision making ⋮ Nonnegative polynomials and sums of squares ⋮ Computing the distance between the linear matrix pencil and the completely positive cone ⋮ Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel ⋮ On the complexity of Putinar-Vasilescu's Positivstellensatz ⋮ Semidefinite representation of convex sets ⋮ Positivity certificates and polynomial optimization on non-compact semialgebraic sets ⋮ Convex sets with semidefinite representation ⋮ A few more extensions of Putinar's Positivstellensatz to non-compact sets ⋮ Certifying the global optimality of quartic minimization over the sphere ⋮ Real algebraic geometry with a view toward systems control and free positivity. Abstracts from the workshop held April 6--12, 2014. ⋮ Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals ⋮ Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity ⋮ On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets ⋮ Partitioning procedure for polynomial optimization ⋮ An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization ⋮ Generating exact nonlinear ranking functions by symbolic-numeric hybrid method ⋮ On the effective Putinar's Positivstellensatz and moment approximation ⋮ A hierarchy of spectral relaxations for polynomial optimization ⋮ Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023 ⋮ A new scheme for approximating the weakly efficient solution set of vector rational optimization problems ⋮ On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity ⋮ A quantitative version of Catlin-D'Angelo-Quillen theorem ⋮ An exact Jacobian SDP relaxation for polynomial optimization ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ Polynomials of almost normal arguments in \(C^*\)-algebras ⋮ Computation of Sum of Squares Polynomials from Data Points ⋮ Rational certificates of non-negativity on semialgebraic subsets of cylinders ⋮ Degree Bounds for Putinar’s Positivstellensatz on the Hypercube ⋮ A toric positivstellensatz with applications to delay systems ⋮ An effective version of Schmüdgen's Positivstellensatz for the hypercube ⋮ Certifying convergence of Lasserre's hierarchy via flat truncation ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients ⋮ A version of Putinar's Positivstellensatz for cylinders ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Computable Primal and Dual Bounds for Stochastic Control ⋮ A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis ⋮ On solving a class of fractional semi-infinite polynomial programming problems ⋮ A new proof for the existence of degree bounds for Putinar’s Positivstellensatz ⋮ Convergence rates of moment-sum-of-squares hierarchies for optimal control problems ⋮ Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ Norm bounds and underestimators for unconstrained polynomial integer minimization ⋮ Exact Certification in Global Polynomial Optimization Via Rationalizing Sums-Of-Squares ⋮ Global minimization of rational functions and the nearest GCDs ⋮ On the exactness of Lasserre relaxations and pure states over real closed fields ⋮ A hierarchy of semidefinite relaxations for completely positive tensor optimization problems ⋮ The CP-Matrix Approximation Problem ⋮ Matrix convex hulls of free semialgebraic sets ⋮ On exact Reznick, Hilbert-Artin and Putinar's representations ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization ⋮ A semidefinite programming approach for solving multiobjective linear programming ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Linear optimization with cones of moments and nonnegative polynomials ⋮ Moment methods in energy minimization: New bounds for Riesz minimal energy problems ⋮ On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems ⋮ Semi-algebraic approximation using Christoffel-Darboux kernel ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ Positive Gorenstein ideals ⋮ Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere ⋮ On an extension of Pólya's Positivstellensatz ⋮ Error bounds for polynomial optimization over the hypercube using Putinar type representations

Uses Software

• Sostools
• SeDuMi
• GloptiPoly
• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
• On the complexity of Schmüdgen's Positivstellensatz
• The \(K\)-moment problem for compact semi-algebraic sets
• Sparsity in sums of squares of polynomials
• Representations of non-negative polynomials having finitely many zeros
• Distinguished representations of non-negative polynomials
• Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets
• Minimizing polynomials via sum of squares over the gradient ideal
• Complexity estimates for the Schmüdgen Positivstellensatz
• Global Optimization with Polynomials and the Problem of Moments
• Distinguished representations of strictly positive polynomials
• Semidefinite optimization
• Optimization of Polynomial Functions
• SOSTOOLS and Its Control Applications
• Optimization of Polynomials on Compact Semialgebraic Sets
• GloptiPoly
• Semidefinite Approximations for Global Unconstrained Polynomial Optimization
• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
• An algorithmic approach to Schmüdgen's Positivstellensatz

This page was built for publication: On the complexity of Putinar's Positivstellensatz