Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces

Abstract

This paper studies the problem of minimizing a homogeneous polynomial (form) f(x) over the unit sphere $\mathbb{S}^{n - 1} = \left\{ {x \in \mathbb{R}^n :\left\| x \right\|_2 = 1} \right\}$. The problem is NP-hard when f(x) has degree 3 or higher. Denote by f_min (resp. f_max) the minimum (resp. maximum) value of f(x) on $\mathbb{S}^{n - 1}$. First, when f(x) is an even form of degree 2d, we study the standard sum of squares (SOS) relaxation for finding a lower bound of the minimum f_min: $\max \gamma s.t. f\left( x \right) - \gamma \cdot \left\| x \right\|_2^{2d} is SOS.$ Let f_sos be the above optimal value. Then we show that for all n ⩾ 2d, $1 \leqslant \frac{{f_{\max } - f_{sos} }}{{f_{\max } - f_{\min } }} \leqslant C(d)\sqrt {\left( {_{2d}^n } \right)} .$ Here, the constant C(d) is independent of n. Second, when f(x) is a multi-form and $\mathbb{S}^{n - 1}$ becomes a multi-unit sphere, we generalize the above SOS relaxation and prove a similar bound. Third, when f(x) is sparse, we prove an improved bound depending on its sparsity pattern; when f(x) is odd, we formulate the problem equivalently as minimizing a certain even form, and prove a similar bound. Last, for minimizing f(x) over a hypersurface H(g) = {x ∈ ℝⁿ: g(x) = 1} defined by a positive definite form g(x), we generalize the above SOS relaxation and prove a similar bound.

Keywords

Approximation bound / form / hypersurface / L²-norm / G-norm / multi-form / polynomial / semidefinite programming / sum of squares

References

[1] Blekherman G. There are significantly more nonnegative polynomials than sums of squares. Israel J Math, 2006, 153: 355-380

[2] Faybusovich L. Floudas C., Pardalos P. Global optimization of homogeneous polynomials on the simplex and on the sphere. Frontiers in Global Optimization. Nonconvex Optim Appl, Vol 74, 2004, Boston: Kluwer Academic Publishers, 109-121

[3] Hurwitz A. Über den Vergleich des arithmetischen und des geometrischen. Mittels J Reine Angew Math, 1891, 108: 266-268

[4] Kojima M., Kim S., Waki H. Sparsity in sums of squares of polynomials. Math Program, 2005, 103(1): 45-62

[5] Lasserre J. Global optimization with polynomials and the problem of moments. SIAM J Optim, 2001, 11(3): 796-817

[6] Ling C., Nie J., Qi L., Ye Y. Bi-quadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J Optim, 2009, 20(3): 1286-1310

[7] Nesterov Y. Random walk in a simplex and quadratic optimization over convex polytopes, 2003, Louvainla-Neuve, Belgium: CORE, Catholic University of Louvain

[8] Nie J., Demmel J. Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J Optim, 2008, 19(4): 1534-1558

[9] Parrilo P. Semidefinite Programming relaxations for semialgebraic problems. Math Program, Ser B, 2003, 96(2): 293-320

[10] Parrilo P. Exploiting structure in sum of squares programs. In: Proceedings for the 42nd IEEE Conference on Decision and Control, Maui, Hawaii, 2003. 2004, 4664–4669

[11] Parrilo P., Sturmfels B. Basu S., Gonzalez-Vega L. Minimizing polynomial functions. Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science (March 2001), 2003, Providence: Amer Math Soc, 83-100

[12] Reznick B. Forms derived from the arithmetic-geometric inequality. Math Ann, 1989, 283: 431-464

[13] Reznick B. Some concrete aspects of Hilbert’s 17^th problem. Contem Math, Vol 253, 2000, Providence: Amer Math Soc, 251-272

[14] Wolkowicz H., Saigal R., Vandenberghe L. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. International Series in Operations Research & Management Science, 27, 2000, Boston: Kluwer Academic Publishers