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-\mathrm{1}}=\{x\in {ℝ}^n:{\Vert x\Vert }_{\mathrm{2}}=|\mathrm{1}\}. 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-\mathrm{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(x)-\gamma ·{\Vert x\Vert }_{\mathrm{2}}^{\mathrm{2}d}isSOS.

Let f_sos be the above optimal value. Then we show that for all n≥2d,

\mathrm{1}\le {\displaystyle \frac{f_{\max }-f_{sos}}{f_{\max }-f_{\min }}}\le C(d)\sqrt{\left(\begin{array}{l}n\\ \mathrm{2}d\end{array}\right)}.

Here, the constant C(d) is independent of n. Second, when f(x) is a multi-form and {\mathbb{S}}^{n-\mathrm{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\in {ℝ}^n:g(x)=\mathrm{1}\} defined by a positive definite form g(x), we generalize the above SOS relaxation and prove a similar bound.

Key words： 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. Global optimization of homogeneous polynomials on the simplex and on the sphere. In: Floudas C, Pardalos P, eds. Frontiers in Global Optimization. Nonconvex Optim Appl, Vol 74. Boston: Kluwer Academic Publishers, 2004, 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. CORE Discussion Paper, CORE, Catholic University of Louvain, Louvainla-Neuve, Belgium, 2003

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 346 Jiawang NIE

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. Minimizing polynomial functions. In: Basu S, Gonzalez-Vega L, eds. Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science (March 2001). Providence: Amer Math Soc, 2003, 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 17th problem. In: Contem Math, Vol 253. Providence: Amer Math Soc, 2000, 251–272

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