Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization

Lucas Slot, Monique LaurentMath. Program 2021 · OpenReview

Introduction

Finding the global minimum of a multivariate polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$ is a fundamental challenge in optimization, encountered in fields ranging from control theory to machine learning. While generally NP-hard, the Lasserre hierarchy—a sequence of semidefinite programming (SDP) relaxations based on Sum-of-Squares (SOS) polynomials—has emerged as a powerful tool for obtaining converging upper and lower bounds. However, the standard multivariate hierarchy suffers from the "curse of dimensionality," as the size of the SDP grows combinatorially with the number of variables and the degree of the polynomials.

The Univariate Measure-Based Hierarchy

To address computational bottlenecks, Jean Lasserre recently proposed a "weaker but cheaper" hierarchy (2019). Instead of multivariate SOS polynomials, this approach utilizes univariate SOS polynomials applied to the push-forward measure of the Lebesgue measure on $K$ by the polynomial $f$. Specifically, it considers a hierarchy of upper approximations that reduces the problem to an eigenvalue problem of size $r+1$. This is a significant improvement over the multivariate version, which requires matrices of size $\binom{n+r}{r}$, making it far more scalable for high-dimensional problems.

Convergence Analysis: Upper and Lower Bounds

The primary contribution of this work is the rigorous analysis of the convergence rate of this univariate hierarchy.

Upper Bound

The authors prove that the error between the $r$-th bound and the true global minimum $f_{min}$ converges at a rate of: $$ \Sigma_r - f_{min} = O\left(\frac{\log^2 r}{r^2}\right) $$ This result holds whenever the set $K$ satisfies a "fatness" condition (Assumption 1). This condition ensures that the set $K$ has sufficient volume near the minimizer, which is true for convex bodies and most compact semialgebraic sets with dense interiors. This improves upon previous results that were limited to specific geometries like the hypercube or the ball.

Lower Bound and Near-Optimality

To determine the tightness of this analysis, the authors establish a lower bound. By exploiting the connection between these bounds and the roots of orthogonal polynomials (specifically Jacobi-type polynomials), they show that for certain polynomials on $K = [-1, 1]$, the convergence rate is at least: $$ \Sigma_r - f_{min} = \Omega\left(\frac{1}{r^2}\right) $$ This demonstrates that the $O(\log^2 r / r^2)$ rate is near-optimal, with only a small logarithmic factor remaining as a potential gap.

Methodological Innovations

The proof strategy relies on several key mathematical constructions:

  1. Needle Polynomials: To establish the upper bound, the authors construct explicit SOS densities using "needle polynomials." These polynomials peak sharply at the global minimizer while remaining negligible elsewhere, effectively approximating a Dirac delta distribution.
  2. Geometric Analysis: The introduction of a geometric parameter allows the analysis to quantify how "cusps" or thin regions in $K$ affect the convergence speed, ensuring the results apply to a wide class of compact sets.
  3. Push-forward Measure: By shifting the focus from the domain $K$ to the distribution of values of $f$, the authors simplify the multivariate complexity into a univariate framework without sacrificing significant theoretical accuracy.

Conclusion

This research bridges the gap between the computational efficiency of univariate measure-based bounds and their theoretical performance. By proving a near-optimal convergence rate of $O(\log^2 r / r^2)$, the authors provide a strong theoretical justification for using these "cheaper" hierarchies in large-scale polynomial optimization problems where standard multivariate SOS methods are computationally prohibitive. Numerical tests on standard benchmarks like the MaxCut problem further validate that this efficiency does not come at the cost of practical accuracy.

Summary updated

Abstract

We consider a hierarchy of upper approximations for the minimization of a polynomial f over a compact set \(K \subseteq \mathbb {R}^n\) proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on K by the polynomial f and involves univariate sums of squares of polynomials with growing degrees 2r. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864–885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of f at a rate in \(O(\log ^2 r / r^2)\) whenever K satisfies a mild geometric condition, which holds, eg., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in \(\varOmega (1/r^2)\) for a class of polynomials on \(K=[-1,1]\), obtained by exploiting a connection to orthogonal polynomials.
BibTeX
@inproceedings{slot2021near,
  author = {Lucas Slot and Monique Laurent},
  title = {{Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization}},
  booktitle = {Math. Program},
  year = {2021},
  url = {https://openreview.net/forum?id=bPcfdVin0v},
}
Figure