×

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
PDF BibTeX Cite
Full Text: DOI
References:
[1] Blekherman G. There are significantly more nonnegative polynomials than sums of squares. Israel J Math, 2006, 153: 355–380 · Zbl 1139.14044
[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 · Zbl 1165.90592
[3] Hurwitz A. Über den Vergleich des arithmetischen und des geometrischen. Mittels J Reine Angew Math, 1891, 108: 266–268 · JFM 23.0263.01
[4] Kojima M, Kim S, Waki H. Sparsity in sums of squares of polynomials. Math Program, 2005, 103(1): 45–62 · Zbl 1079.90092
[5] Lasserre J. Global optimization with polynomials and the problem of moments. SIAM J Optim, 2001, 11(3): 796–817 · Zbl 1010.90061
[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 · Zbl 1221.90074
[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 · Zbl 1178.65048
[9] Parrilo P. Semidefinite Programming relaxations for semialgebraic problems. Math Program, Ser B, 2003, 96(2): 293–320 · Zbl 1043.14018
[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 · Zbl 1099.13516
[12] Reznick B. Forms derived from the arithmetic-geometric inequality. Math Ann, 1989, 283: 431–464 · Zbl 0637.10015
[13] 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
[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 · 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.