Abstract
We consider the problem of computing the minimum value $f_{\min, K}$ of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$. This problem can be reformulated as finding a probability measure $\nu$ on $K$ that minimizes the integral $\int_K f d\nu$. Lasserre demonstrated that it suffices to consider measures of the form $\nu = q\mu$, where $q$ is a sum-of-squares (SOS) polynomial and $\mu$ is a given Borel measure supported on $K$. By bounding the degree of $q$ by $2r$, one obtains a converging hierarchy of upper bounds $f^{(r)}$ for $f_{\min, K}$. While rates of $O(1/r^2)$ were known for specific cases like the hypercube with Chebyshev measures, this paper extends such error estimates to a wider class of convex bodies and reference measures, including the Lebesgue measure. We establish new convergence rates of $O(1/r^2)$ for simplices and balls, $O(\log r / r)$ for sets satisfying mild geometric conditions, and $O(\log^2 r / r^2)$ for general convex bodies, significantly improving upon previous $O(1/\sqrt{r})$ and $O(1/r)$ estimates.
Introduction
Finding the global minimum of a polynomial $f$ over a compact set $K$ (such as a cube, ball, or simplex) is a fundamental challenge in optimization, often classified as NP-hard. Lasserre’s hierarchy has emerged as a powerful framework for addressing this, typically focusing on lower bounds via Sum-of-Squares (SOS) programming. However, Lasserre also proposed a hierarchy of upper bounds based on measure theory. These bounds are constructed by searching for a probability measure that minimizes the integral of $f$, specifically using measures of the form $\nu = q\mu$, where $q$ is an SOS polynomial and $\mu$ is a standard reference measure (like the Lebesgue measure). The efficiency of this approach depends on the convergence rate of these upper bounds to the true minimum as the degree of $q$ increases.
Methodology: Local Similarity and Needle Polynomials
To refine the convergence analysis, this research introduces two innovative strategies that shift the focus from global properties to local behavior:
- Local Similarity and Transportation: The authors demonstrate that the convergence rate is primarily determined by the local geometry of $K$ near the global minimizer. If a complex set "looks like" a simpler set (such as a ball or hypercube) in the immediate neighborhood of the minimizer, the fast convergence rates associated with the simpler geometry can be transferred to the more complex domain.
- Needle Polynomials: Moving beyond traditional techniques that used Taylor expansions of Gaussian functions, the authors utilize needle polynomials. These are univariate polynomials derived from Chebyshev polynomials designed to concentrate their "mass" around the minimizer while remaining negligible elsewhere. These polynomials are "sharper" than Gaussian approximations for a fixed degree, enabling much tighter error estimates.
Key Results
The primary contribution of this work is the establishment of significantly improved "speed limits" for the error $E^{(r)}$, representing the gap between the $r$-th bound and the true minimum. Notably, the $O(1/r^2)$ rate—previously associated only with specific cases like the hypercube—is shown to apply to a much broader range of geometries, including the unit ball and simplices.
As shown in the table above, the authors improve the general estimate for sets satisfying "Assumption 1" from $O(1/\sqrt{r})$ to $O(\log r / r)$ and for general convex bodies from $O(1/r)$ to $O(\log^2 r / r^2)$. Numerical experiments on non-standard shapes like octagons confirm these theoretical findings, suggesting that the $O(1/r^2)$ rate may be even more universal than currently proven.
Conclusion and Future Work
This paper provides a significant theoretical upgrade to Lasserre’s measure-based hierarchy, proving that these upper bounds converge much faster than previously estimated for common geometric shapes. While the authors suspect the logarithmic factors in the general convex body estimates might be artifacts of the proof technique, the current results already establish new benchmarks for global optimization. Future work remains to extend these results to more complex polytopes and non-polynomial functions, such as rational or Lipschitz continuous functions.
Summary updated