On the complexity of Schmüdgen's Positivstellensatz
From MaRDI portal
Publication:876820
DOI10.1016/J.JCO.2004.01.005zbMATH Open1161.68480OpenAlexW2137508197MaRDI QIDQ876820FDOQ876820
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
Recommendations
- Complexity estimates for the Schmüdgen Positivstellensatz
- A new proof for the existence of degree bounds for Putinar's positivstellensatz
- An algorithmic approach to Schmüdgen's Positivstellensatz
- An effective version of Schmüdgen's Positivstellensatz for the hypercube
- On the complexity of Putinar's Positivstellensatz
complexitymoment problempositive polynomialsum of squaresPositivstellensatzpreorderingoptimization of polynomials
Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)
Cites Work
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Title not available (Why is that?)
- The \(K\)-moment problem for compact semi-algebraic sets
- Uniform denominators in Hilbert's seventeenth problem
- An effective version of Pólya's theorem on positive definite forms
- Title not available (Why is that?)
- Optimization of Polynomials on Compact Semialgebraic Sets
- A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
- Complexity estimates for the Schmüdgen Positivstellensatz
- Title not available (Why is that?)
- Optimization of Polynomial Functions
- Effective Łojasiewicz inequalities in semialgebraic geometry
- Positive polynomials on compact sets
- Distinguished representations of strictly positive polynomials
- An algorithmic approach to Schmüdgen's Positivstellensatz
- Complexity estimates for representations of Schmüdgen type.
Cited In (47)
- Convexifying Positive Polynomials and Sums of Squares Approximation
- Characterization of polynomials whose large powers have all positive coefficients
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Matrix convex hulls of free semialgebraic sets
- Stability of quadratic modules
- Łojasiewicz inequalities with explicit exponents for smallest singular value functions
- On the complexity of Putinar's Positivstellensatz
- Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets
- On an extension of Pólya's Positivstellensatz
- The moment-SOS hierarchy: applications and related topics
- Metric properties of semialgebraic mappings
- Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
- A version of Putinar's Positivstellensatz for cylinders
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- A semidefinite programming approach for solving multiobjective linear programming
- Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
- A real Nullstellensatz and Positivstellensatz for the semipolynomials over an ordered field
- An effective version of Schmüdgen's Positivstellensatz for the hypercube
- Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets
- A few more extensions of Putinar's Positivstellensatz to non-compact sets
- Certifying the global optimality of quartic minimization over the sphere
- A new proof for the existence of degree bounds for Putinar’s Positivstellensatz
- A hierarchy of spectral relaxations for polynomial optimization
- Rational certificates of non-negativity on semialgebraic subsets of cylinders
- Error bounds for polynomial optimization over the hypercube using Putinar type representations
- An exact Jacobian SDP relaxation for polynomial optimization
- Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
- On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
- Polynomials of almost normal arguments in \(C^*\)-algebras
- Real algebraic geometry with a view toward systems control and free positivity. Abstracts from the workshop held April 6--12, 2014.
- Exact algorithms for linear matrix inequalities
- Positivstellensätze for polynomial matrices
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Convergence rates for sums-of-squares hierarchies with correlative sparsity
- Semidefinite representation of convex sets
- On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity
- Minimum ellipsoid bounds for solutions of polynomial systems via sum of squares
- Semidefinite programming for min-max problems and games
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
- On the minimum of a positive polynomial over the standard simplex
- On the effective Putinar's Positivstellensatz and moment approximation
- On the Generation of Positivstellensatz Witnesses in Degenerate Cases
- Effective Pólya semi-positivity for non-negative polynomials on the simplex
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
- On the complexity of Putinar-Vasilescu's Positivstellensatz
- Convex sets with semidefinite representation
This page was built for publication: On the complexity of Schmüdgen's Positivstellensatz
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876820)
