Abstract
We compare algorithms for global optimization of polynomial functions in many variables. It is demonstrated that existing algebraic methods (Gröbner bases, resultants, homotopy methods) are dramatically outperformed by a relaxation technique, due to N.Z. Shor and the first author, which involves sums of squares and semidefinite programming. This opens up the possibility of using semidefinite programming relaxations arising from the Positivstellensatz for a wide range of computational problems in real algebraic geometry.
The Bézout Bottleneck
The fundamental challenge in global optimization of a multivariate polynomial $f(x_1, \dots, x_n)$ is identifying the global minimum $f^*$. Classical algebraic geometry approaches this by finding all "critical points"—where the gradient $\nabla f$ vanishes—and evaluating $f$ at each real critical point.
However, the number of such points, known as the Bézout number, grows exponentially with the number of variables and the degree of the polynomial. For a dense polynomial of degree $2d$ in $n$ variables, there are $(2d-1)^n$ complex critical points. As shown in Table 1, even for moderate $n$ and $d$, the number of points to track becomes astronomical, rendering methods like Gröbner bases or numerical homotopy infeasible for even moderately sized problems.
From Roots to Sum of Squares (SOS)
To bypass this bottleneck, the authors employ a relaxation technique based on Sum of Squares (SOS). Instead of finding roots, we seek the largest $\lambda$ such that $f(x) - \lambda$ is non-negative. A sufficient condition for non-negativity is that the polynomial can be written as a sum of squares of other polynomials.
Finding this lower bound, $f_{sos}$, can be formulated as a Semidefinite Programming (SDP) problem. The complexity of this approach is determined by the size of the Gram matrix, which corresponds to the number of monomials of degree at most $d$. Crucially, this size grows only polynomially with the number of variables $n$, as illustrated in Table 2. Unlike finding roots, SDPs can be solved in polynomial time using interior-point methods.
Performance and Scaling
The practical impact of this shift in perspective is significant. In comparative tests, the performance gap between methods is stark:
- Homotopy Methods: Solving a quartic in 7 variables ($n=7, 2d=4$) took 526 seconds. For $n=9$, the method became effectively impossible due to the exponential path count.
- SDP Methods: The same $n=7$ problem was solved in just 4.4 seconds.
The authors successfully optimized quartic problems with up to $n=15$ variables in a few hours. For context, the Bézout number for this case is over 14 million, making algebraic methods completely impossible.
Conclusion and Future Directions
While the SOS relaxation is not always exact (e.g., the Motzkin polynomial), it proved tight for the vast majority of random test cases. By linking practical optimization to deep results in real algebraic geometry like the Positivstellensatz, this work establishes SDP as a powerful tool for a wide range of computational problems. Future research focuses on exploiting polynomial structure, such as sparsity and symmetry, to further reduce the size of SDP matrices and scale to even larger systems.
This paper was presented at the Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, held at DIMACS, Rutgers University, March 12-16, 2001.
Summary updated