Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization
We study the convergence rate of the moment-SOS (sum-of-squares) hierarchy for polynomial optimization problems (POPs) on a bounded subset of the real line described by arbitrary polynomial inequalities. We prove that, for every fixed univariate POP, the relaxation error is bounded by $O(1/r^2)$, where $r$ is the relaxation order. In particular, boundary degeneracies in the polynomial description of the feasible set affect the constant but not the convergence exponent. The proof combines the structure of finitely generated univariate quadratic modules with a Chebyshev polynomial construction…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.20544
curl -X POST /api/v1/records/arxiv/2609.20544/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20544/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'