On the complexity of Schmüdgen's Positivstellensatz

DOI10.1016/J.JCO.2004.01.005zbMath1161.68480OpenAlexW2137508197MaRDI QIDQ876820

Markus Schweighofer

Publication date: 30 April 2007

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

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:352-156518

zbMATH Keywords

complexitymoment problemPositivstellensatzpreorderingpositive polynomialsum of squaresoptimization of polynomials

Mathematics Subject Classification ID

Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Semialgebraic sets and related spaces (14P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real algebra (13J30)

Related Items (41)

Łojasiewicz inequalities with explicit exponents for smallest singular value functions ⋮ Stability of quadratic modules ⋮ Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel ⋮ Metric properties of semialgebraic mappings ⋮ On the complexity of Putinar-Vasilescu's Positivstellensatz ⋮ Convexifying Positive Polynomials and Sums of Squares Approximation ⋮ Semidefinite representation of convex sets ⋮ Certificates for nonnegativity of polynomials with zeros on 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. ⋮ On the complexity of Putinar's Positivstellensatz ⋮ On the effective Putinar's Positivstellensatz and moment approximation ⋮ A hierarchy of spectral relaxations for polynomial optimization ⋮ Characterization of polynomials whose large powers have all positive coefficients ⋮ On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity ⋮ An exact Jacobian SDP relaxation for polynomial optimization ⋮ Polynomials of almost normal arguments in \(C^*\)-algebras ⋮ Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials ⋮ Rational certificates of non-negativity on semialgebraic subsets of cylinders ⋮ Degree Bounds for Putinar’s Positivstellensatz on the Hypercube ⋮ An effective version of Schmüdgen's Positivstellensatz for the hypercube ⋮ A version of Putinar's Positivstellensatz for cylinders ⋮ A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis ⋮ Semidefinite programming for min-max problems and games ⋮ A new proof for the existence of degree bounds for Putinar’s Positivstellensatz ⋮ Effective Pólya semi-positivity for non-negative polynomials on the simplex ⋮ 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 ⋮ On the minimum of a positive polynomial over the standard simplex ⋮ Matrix convex hulls of free semialgebraic sets ⋮ 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 ⋮ On the Generation of Positivstellensatz Witnesses in Degenerate Cases ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ On an extension of Pólya's Positivstellensatz ⋮ Error bounds for polynomial optimization over the hypercube using Putinar type representations ⋮ Minimum ellipsoid bounds for solutions of polynomial systems via sum of squares

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(K\)-moment problem for compact semi-algebraic sets
• Effective Łojasiewicz inequalities in semialgebraic geometry
• Complexity estimates for representations of Schmüdgen type.
• Uniform denominators in Hilbert's seventeenth problem
• An effective version of Pólya's theorem on positive definite forms
• Complexity estimates for the Schmüdgen Positivstellensatz
• Global Optimization with Polynomials and the Problem of Moments
• Distinguished representations of strictly positive polynomials
• Optimization of Polynomial Functions
• Optimization of Polynomials on Compact Semialgebraic Sets
• Positive polynomials on compact sets
• 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 Schmüdgen's Positivstellensatz