Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube

Abstract

We revisit the problem of minimizing a given polynomial $f$ on the hypercube $[-1,1{]}^n$. Lasserre's hierarchy (also known as the moment- or sum-of-squares hierarchy) provides a sequence of lower bounds $\{f_{(r)}{\}}_{r\in \mathbb{N}}$ on the minimum value $f^{\ast }$, where $r$ refers to the allowed degrees in the sum-of-squares hierarchy. A natural question is how fast the hierarchy converges as a function of the parameter $r$. The current state-of-the-art is due to Baldi and Slot [SIAM J. on Applied Algebraic Geometry, 2024] and roughly shows a convergence rate of order $1/r$. Here we obtain closely related results via a different approach: the polynomial kernel method. We also discuss limitations of the polynomial kernel method, suggesting a lower bound of order $1/r^2$ for our approach.

24 pages, 3 figures