Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization
Abstract
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/r2), 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 that approximately recovers the natural generators of the feasible set while controlling the degree of the certificate. We also give an elementary degree-four example for which the relaxation error is exactly $1/(2r(r-1))$, showing that the quadratic rate is optimal. Equivalent reformulations connect this example to a cubic univariate problem and to a bivariate POP whose feasible set has a cusp singularity at the minimizer.
Related
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- Optimality and Exact Moment-SDP Formulations for Robust Two-Stage Convex Polynomial Multiobjective Optimization
- A Bounded Degree SOS Plus SONC Hierarchy for Polynomial Optimization
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- The Matricial Univariate Rational Truncated Moment Problem
BibTeX
@misc{henrion2026convergence,
title = {{Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization}},
author = {Didier Henrion and Mohab Safey El Din},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20544},
eprint = {2609.20544},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05733870v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization
AU - Didier Henrion
AU - Mohab Safey El Din
PY - 2026
DA - 2026/09/01
PB - HAL
DO - 10.48550/arxiv.2609.20544
UR - https://hal.science/hal-05733870v1
AB - 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 that approximately recovers the natural generators of the feasible set while controlling the degree of the certificate. We also give an elementary degree-four example for which the relaxation error is exactly $1/(2r(r-1))$, showing that the quadratic rate is optimal. Equivalent reformulations connect this example to a cubic univariate problem and to a bivariate POP whose feasible set has a cusp singularity at the minimizer.
ER -