Erlangen Hub Seminar: Beyond Second-Order Methods: Sum-of-Squares, Tensor Methods, and AI for Polynomial Optimization, Kate Wenqi Zhu
Hilbert’s seventeenth problem famously showed that not every nonnegative polynomial admits a sum-of-squares (SoS) representation. Hilbert also identified several special classes for which nonnegativity and SoS are equivalent, including univariate polynomials, quadratic polynomials, and bivariate quartics.
In this talk, we will extend this connection to new classes of multivariate quartically regularized polynomials arising as subproblems in high-order tensor methods for nonconvex optimization. In particular,we will show that, under mild conditions and for sufficiently large regularization parameters, globally nonnegative quartically regularized cubic polynomials admit exact SoS certificates. We will also discuss structured subclasses for which this equivalence holds for every positive regularization parameter, together with counterexamples demonstrating the crucial role played by Euclidean regularization. These results lead naturally to tractable high-order optimization frameworks based on SoS and SoS-convex Taylor models, in which each regularized polynomial subproblem can be solved in polynomial time. Finally, we will briefly discuss an AI-integrated approach to polynomial nonnegativity and SoS reasoning, including a specialised dataset and fine-tuned language model designed to tackle these computationally challenging mathematical problems.