TL;DR
This paper demonstrates that global optimization of multivariate polynomials—traditionally a "hard" problem plagued by exponential complexity—can be efficiently tackled using Sum of Squares (SOS) relaxations. By shifting the problem from finding all critical points to solving Semidefinite Programs (SDP), the authors show that we can solve problems with up to 15 variables that were previously computationally impossible.
What Problem Does This Paper Address?
The authors tackle the fundamental problem of finding the global minimum $f^*$ of a multivariate polynomial $f(x_1, \dots, x_n)$.
In classical algebraic geometry, the standard way to find a minimum is to find all "critical points" (where the gradient is zero) and check which one yields the lowest value. However, the number of these points—known as the Bézout number—grows exponentially with the number of variables and the degree of the polynomial. For a dense quartic polynomial in 10 variables, there are nearly 60,000 complex critical points to track. This "Bézout bottleneck" makes traditional methods like Gröbner bases or numerical homotopy infeasible for even moderately sized problems.
Methods
The paper compares two major paradigms:
- Exact Algebraic Methods: These include Gröbner bases, resultants, and numerical homotopy methods. These methods attempt to find every single critical point (even complex ones) to identify the real global minimum.
- Sum of Squares (SOS) Relaxation: This approach, pioneered by N.Z. Shor and expanded by Pablo Parrilo, asks a different question: "What is the largest number $\lambda$ such that $f(x) - \lambda$ can be written as a sum of squares of other polynomials?"
If a polynomial is a sum of squares, it is guaranteed to be non-negative. Finding this $\lambda$ (denoted $f_{sos}$) can be cast as a Semidefinite Programming (SDP) problem. Unlike finding roots, SDPs can be solved in polynomial time (for a fixed degree) using interior-point methods.
Datasets
The authors evaluated their methods using a synthetic family of test polynomials:
- Structure: $f(x_1, \dots, x_n) = \sum_{i=1}^n x_i^{2d} + g(x_1, \dots, x_n)$, where $g$ is a random polynomial of lower degree.
- Design: This structure ensures the function is "bounded below" (it doesn't go to negative infinity) and has a well-defined global minimum.
- Scale: They tested various combinations of $n$ (variables) and $2d$ (degree), ranging from small cases to $n=15$ for quartics.
Key Insights and Ideas
- The Power of Relaxation: While $f_{sos}$ is technically only a lower bound ($f_{sos} \le f^*$), the authors found that in practice, for their random test cases, the bound was almost always tight ($f_{sos} = f^*$).
- Complexity Scaling: The size of the matrices in the SDP approach grows polynomially with $n$, whereas the number of paths in homotopy methods grows exponentially. This makes SDP the clear winner for "many-variable" problems.
- Duality as a Certificate: The dual of the SDP problem provides a way to extract the actual point $p^*$ where the minimum occurs. If the relaxation is tight, the SDP solver returns a "certificate" of optimality.
- Connection to the Positivstellensatz: The authors link these practical optimization techniques to deep results in real algebraic geometry (like the Positivstellensatz), suggesting that SDP can be used to solve a much wider range of problems, such as proving that a set of polynomial inequalities has no solution.
Key Results
The performance gap between the methods is stark:
- Homotopy Methods: For a quartic in 7 variables ($n=7, 2d=4$), the homotopy method took 526 seconds. For $n=9$, it became effectively infeasible.
- SDP Methods: For the same $n=7$ case, the SDP approach took only 4.4 seconds.
- Scaling: The authors successfully solved quartic problems with $n=15$ variables using SDP in a few hours. For context, the Bézout number for this case is over 14 million, making algebraic methods completely impossible.
Limitations and Future Work
- Not Always Exact: The authors acknowledge that $f_{sos}$ does not always equal $f^*$. Famous examples like the Motzkin polynomial are non-negative but cannot be written as a sum of squares. In such cases, "higher-degree relaxations" are needed, which increase computational cost.
- Numerical Stability: Large coefficients in random polynomials can lead to ill-conditioned matrices, requiring careful scaling of the input data.
- Exploiting Structure: Future work involves adapting these methods for "sparse" polynomials (those with few terms) or polynomials with symmetry, which could further reduce the size of the SDP matrices and allow for even larger problems to be solved.
Reference: Parrilo, P. A., & Sturmfels, B. (2001). Minimizing Polynomial Functions. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
Summary updated