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

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\).