pipette
ENEnglish

Optimal degree bounds for sum-of-squares representations

Alexander Taveira Blomenhofer, Sander Gribling, Didier Henrion, Milan Korda, Poornendu Kumar, Victor Magron, Lucas Slot, Luis Felipe Vargas, Juan Vera

Preprint

En palabras de los autores

The moment-sum-of-squares (SOS) hierarchy provides a sequence of bounds on the minimum of a polynomial over a basic closed semialgebraic set, i.e., a subset of defined by finitely many polynomial constraints. We establish optimal bounds on the error of the SOS hierarchy in the following settings: 1. If the constraints define an Archimedean quadratic module: the error of the Putinar-based hierarchy at level is in the worst case. 2. If the constraints define a compact semialgebraic set: the error of the Schm\"udgen-based hierarchy at level is in the worst case. 3. If the constraints define an Archimedean quadratic module and satisfy linear independence constraint qualification conditions (LICQ): the error of the hierarchy at level is in the worst case. Here, the upper bound holds already for the Putinar-based hierarchy, while the lower bound holds even against the Schm\"udgen-based hierarchy. Equivalently, these give best-possible effective versions of Putinar's and Schm\"udgen's Positivstellens\"atze for these settings (in terms of their dependence on ).

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages, 6 tables