On the complexity of Putinar's Positivstellensatz
classification
🧮 math.AG
math.ACmath.OC
keywords
positivstellensatzboundcomplexitypolynomialputinarconsequenceconstraintsconvergence
read the original abstract
We prove an upper bound on the degree complexity of Putinar's Positivstellensatz. This bound is much worse than the one obtained previously for Schm\"udgen's Positivstellensatz but it depends on the same parameters. As a consequence, we get information about the convergence rate of Lasserre's procedure for optimization of a polynomial subject to polynomial constraints.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra
Explicit convergence rates for noncommutative SOS hierarchies on the Pauli algebra are bounded using smallest roots of Krawtchouk polynomials.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.