Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces (Q693193)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces |
scientific article |
Statements
Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces (English)
0 references
7 December 2012
0 references
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\).
0 references
multi-form
0 references
unit sphere
0 references
multi-unit sphere
0 references
hypersurface
0 references
polynomial
0 references
sum of squares relaxation
0 references
semidefinite programming
0 references
approximation bound
0 references
NP-hard problem
0 references
\(L^2\)-norm
0 references
\(G\)-norm
0 references
algorithm
0 references
0 references