Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
In the authors' words
We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin . For any fixed Archimedean quadratic module with prescribed generators and any fixed bound on the degree of the objective, we prove a uniform certificate-degree upper bound of for normalized polynomial objectives. We show that this bound is sharp by constructing a matching lower-bound example in three variables, thereby establishing that the dependence on is optimal. These matching bounds also yield sharp worst-case convergence rates for the Lasserre hierarchy.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.