Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
研究了将多项式分解为r个平方和的问题，证明对于单变量多项式，当r≥2时，目标函数没有虚假二阶临界点，所有局部最优都是全局最优。
.We study the problem of decomposing a polynomial \(p\) into a sum of \(r\) squares by minimizing a quadratically penalized objective \(f_p(\boldsymbol{\mathbf{u}}) = \left \lVert \sum_{i=1}^r u_i^2 - p \right \lVert^2\). This objective is nonconvex and is equivalent to the rank-\(r\) Burer–Monteiro factorization of a semidefinite program (SDP) encoding the sum of squares decomposition. We show that for all univariate polynomials \(p\), if \(r \ge 2\), then \(f_p(\boldsymbol{\mathbf{u}})\) has no spurious second-order critical points, showing that all local optima are also global optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity conditions, \(r\) has to be roughly the square root of the number of constraints (the degree of \(p\)) for there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-order necessary conditions. We also show that by choosing a norm based on sampling equally spaced points on the circle, the gradient \(\nabla f_p\) can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials.Keywordsnonconvex optimizationsum of squarestrigonometric polynomialsBurer–Monteiro methodglobal landscapesemidefinite programmingMSC codes90C2390C2690C22