Sum-of-Squares Hierarchies for Binary Polynomial Optimization

Lucas Slot, Monique LaurentMath. Program 2021 · OpenReview

Abstract

We consider the sum-of-squares (SOS) hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{B}^n = \{0, 1\}^n$. This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by the largest scalar $\lambda$ for which the polynomial $f - \lambda$ is a sum-of-squares on $\mathbb{B}^n$ with degree at most $2r$. We analyze the quality of these bounds by estimating the worst-case error $f_{\min} - f_{(r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t \in [0, 1/2]$, we show that this worst-case error in the regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{t(1-t)}$ as $n \to \infty$. Our proof combines classical Fourier analysis on $\mathbb{B}^n$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{(r)}$ and another hierarchy of upper bounds $f^{(r)}$, for which we establish the same error analysis. Our results extend to the minimization of polynomials over the $q$-ary cube $(\mathbb{Z}/q\mathbb{Z})^n$ and apply to matrix-valued polynomials.

Introduction

Binary polynomial optimization—minimizing a polynomial $f$ over the $n$-dimensional boolean hypercube $\mathbb{B}^n$—is a cornerstone of combinatorial optimization. Many NP-hard problems, including MAX-CUT and the determination of the stability number of a graph, can be formulated within this framework. To address these challenges, researchers frequently employ the Sum-of-Squares (SOS) hierarchy, also known as the Lasserre hierarchy.

This method generates a sequence of increasingly tight lower bounds $f_{(r)}$ and upper bounds $f^{(r)}$ by solving Semidefinite Programs (SDPs) of degree $2r$. While it is well-established that these bounds become exact when $r$ reaches approximately $n/2$, the behavior of the approximation error in the intermediate regime—where $r$ scales linearly with $n$—has remained largely unquantified. This research provides the first theoretical error analysis for SOS hierarchies in this non-exact regime.

Methodological Framework

The authors utilize a sophisticated blend of harmonic analysis and orthogonal polynomial theory to characterize the convergence of the SOS hierarchy. The approach rests on three primary pillars:

  1. Symmetry Reduction and Fourier Analysis: By exploiting the inherent symmetry of the boolean hypercube, the authors apply Fourier analysis to reduce the search for a multivariate SOS certificate to a univariate problem on the discrete set $\{0, 1, \dots, n\}$. A key tool in this reduction is a discrete analog of the Funk-Hecke formula, typically used in spherical harmonics.
  2. Polynomial Kernel Technique: The authors employ a "kernel" to transform the multivariate optimization problem into a more manageable form, allowing for a direct comparison between the polynomial $f$ and its SOS approximations.
  3. Orthogonal Polynomials: The analysis establishes a fundamental link between the optimization bounds and Krawtchouk polynomials, which are the natural orthogonal polynomials for the discrete measure on the hypercube.

The Krawtchouk Connection and Asymptotic Error

The most significant insight of this work is that the approximation error is fundamentally determined by the least root of the Krawtchouk polynomial of degree $r+1$. This connection transforms a complex optimization question into a problem within the well-studied theory of extremal roots of orthogonal polynomials.

In the regime where the hierarchy order $r$ scales linearly with $n$ (i.e., $r \approx t \cdot n$ for $t \in [0, 1/2]$), the authors demonstrate that the relative error follows a predictable asymptotic curve. Specifically, the error behaves according to the function: $$\phi(t) = \frac{1}{2} - \sqrt{t(1 - t)}$$

This provides a concrete "performance profile" for SOS hierarchies. For a polynomial of degree $d$, the relative error of the $r$-th order SOS bound is bounded by $2C_d \cdot (\xi^n_{r+1}/n)$, where $\xi^n_{r+1}$ is the smallest root of the corresponding Krawtchouk polynomial. The constant $C_d$ is estimated using Chebyshev polynomials and depends solely on the degree $d$, not on the number of variables $n$.

Extensions and Generalizations

The analysis is not limited to scalar polynomials on the boolean cube. The authors demonstrate the universality of their proof strategy by extending it to:

  • $q$-ary Cubes: The results hold for variables taking $q$ discrete values (elements of $\mathbb{Z}/q\mathbb{Z}$).
  • Matrix-Valued Polynomials: The error analysis remains valid when the objective function is a matrix-valued polynomial, expanding the utility of the SOS hierarchy in control theory and quantum information science.

Conclusion and Future Directions

This research provides a granular view of the convergence process of SOS hierarchies, matching known exactness results while filling the gap in the proportional regime. However, several avenues for future work remain. The current analysis is most effective when $r = \Omega(n)$ and provides less insight for very low, constant values of $r$ (e.g., $r=2, 3$) when $n$ is extremely large. Furthermore, the constant $C_d$ grows significantly with the degree $d$, suggesting that refining this dependence could yield tighter bounds for high-degree problems. Finally, extending these kernel-based techniques to sets lacking high symmetry, such as general polytopes or constrained semi-algebraic sets, remains a significant challenge for the field.

Summary updated

Abstract

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube \(\mathbb {B}^{n}=\{0,1\}^n\). This hierarchy provides for each integer \(r \in \mathbb {N}\) a lower bound \(\smash {f_{({r})}}\) on the minimum \(f_{\min }\) of f, given by the largest scalar \(\lambda \) for which the polynomial \(f - \lambda \) is a sum-of-squares on \(\mathbb {B}^{n}\) with degree at most 2r. We analyze the quality of these bounds by estimating the worst-case error \(f_{\min }- \smash {f_{({r})}}\) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed \(t \in [0, 1/2]\), we can show that this worst-case error in the regime \(r \approx t \cdot n\) is of the order \(1/2 - \sqrt{t(1-t)}\) as n tends to \(\infty \). Our proof combines classical Fourier analysis on \(\mathbb {B}^{n}\) with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds \(\smash {f_{({r})}}\) and another hierarchy of upper bounds \(\smash {f^{({r})}}\), for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube \(\mathbb (\mathbb {Z}/ q\mathbb {Z})^{n}\).
BibTeX
@inproceedings{slot2021sum,
  author = {Lucas Slot and Monique Laurent},
  title = {{Sum-of-Squares Hierarchies for Binary Polynomial Optimization}},
  booktitle = {Math. Program},
  year = {2021},
  url = {https://openreview.net/forum?id=HhIcenYARA},
}
Figure