# zbMATH — the first resource for mathematics

Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. (English) Zbl 1277.65046
The paper studies four similar types of problems: (1) minimizing a polynomial form $$f$$ over a unit sphere, (2) minimizing a multi-form $$f$$ over a multi-unit sphere, (3) minimizing a sparse or odd form $$f$$ over a unit sphere, (4) minimizing a homogeneous polynomial $$f$$ over a hypersurface. As the problems are NP-hard, approximation algorithms for solving these types of problems are used. The paper is devoted to the standard sum of squares (SOS) relaxation and its generalizations (it is equivalent to a semidefinite programming problem). For each individual case of minimization the authors discuss the performance of the SOS relaxation by answering the question how well the optimal value $$f_{\mathrm{sos}}$$ of the SOS relaxation approximates the minimum value $$f_{\min}$$ of $$f$$. It is done by analyzing the upper bound for the ratio $$(f_{\max}-f_{\mathrm{sos}})/(f_{\max}-f_{\min})$$ where $$f_{\max}$$ is the maximum value of $$f$$.

##### MSC:
 65K05 Numerical mathematical programming methods 90C22 Semidefinite programming 90C59 Approximation methods and heuristics in mathematical programming
Full Text:
##### References:
  Blekherman G. There are significantly more nonnegative polynomials than sums of squares. Israel J Math, 2006, 153: 355–380 · Zbl 1139.14044  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 · Zbl 1165.90592  Hurwitz A. Über den Vergleich des arithmetischen und des geometrischen. Mittels J Reine Angew Math, 1891, 108: 266–268 · JFM 23.0263.01  Kojima M, Kim S, Waki H. Sparsity in sums of squares of polynomials. Math Program, 2005, 103(1): 45–62 · Zbl 1079.90092  Lasserre J. Global optimization with polynomials and the problem of moments. SIAM J Optim, 2001, 11(3): 796–817 · Zbl 1010.90061  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 · Zbl 1221.90074  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  Nie J, Demmel J. Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J Optim, 2008, 19(4): 1534–1558 · Zbl 1178.65048  Parrilo P. Semidefinite Programming relaxations for semialgebraic problems. Math Program, Ser B, 2003, 96(2): 293–320 · Zbl 1043.14018  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  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 · Zbl 1099.13516  Reznick B. Forms derived from the arithmetic-geometric inequality. Math Ann, 1989, 283: 431–464 · Zbl 0637.10015  Reznick B. Some concrete aspects of Hilbert’s 17th problem. In: Contem Math, Vol 253. Providence: Amer Math Soc, 2000, 251–272 · Zbl 0972.11021  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 · Zbl 0951.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.