pipette
ESEspañol

Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

Yuxiang Zhao, Ting Gan

Preprint

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.