# A practical, fast method for solving sum-of-squares problems for very large polynomials

arXiv: https://arxiv.org/abs/2410.19844 · HTML: https://mlsanity.com/paper/2410.19844/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 32 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 16 of 16)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [Deep Polynomial Neural Networks](https://mlsanity.com/paper/2006.13026/) (2020)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Regularization of polynomial networks for image recognition](https://mlsanity.com/paper/2303.13896/) (2023)
- [Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension](https://mlsanity.com/paper/2003.03210/) (2020)
- [A Faster Interior-Point Method for Sum-of-Squares Optimization](https://mlsanity.com/paper/2202.08489/) (2022)
- [SOSOPT: A Toolbox for Polynomial Optimization](https://mlsanity.com/paper/1308.1889/) (2013)
- [Sum-of-Squares Geometry Processing](https://mlsanity.com/paper/2110.08451/) (2021)
- [Geometry of 3D Environments and Sum of Squares Polynomials](https://mlsanity.com/paper/1611.07369/) (2016)
- [Sum-of-squares optimization without semidefinite programming](https://mlsanity.com/paper/1712.01792/) (2017)
- [Low-Rank Univariate Sum of Squares Has No Spurious Local Minima](https://mlsanity.com/paper/2205.11466/) (2022)

## Abstract (arXiv)

Sum of squares (SOS) optimization is a powerful technique for solving problems where the positivity of a polynomials must be enforced. The common approach to solve an SOS problem is by relaxation to a Semidefinite Program (SDP). The main advantage of this transormation is that SDP is a convex problem for which efficient solvers are readily available. However, while considerable progress has been made in recent years, the standard approaches for solving SDPs are still known to scale poorly. Our goal is to devise an approach that can handle larger, more complex problems than is currently possible. The challenge indeed lies in how SDPs are commonly solved. State-Of-The-Art approaches rely on the interior point method, which requires the factorization of large matrices. We instead propose an approach inspired by polynomial neural networks, which exhibit excellent performance when optimized using techniques from the deep learning toolbox. In a somewhat counter-intuitive manner, we replace the convex SDP formulation with a non-convex, unconstrained, and over parameterized formulation, and solve it using a first order optimization method. It turns out that this approach can handle very large problems, with polynomials having over four million coefficients, well beyond the range of current SDP-based approaches. Furthermore, we highlight theoretical and practical results supporting the experimental success of our approach in avoiding spurious local minima, which makes it amenable to simple and fast solutions based on gradient descent. In all the experiments, our approach had always converged to a correct global minimum, on general (non-sparse) polynomials, with running time only slightly higher than linear in the number of polynomial coefficients, compared to higher than quadratic in the number of coefficients for SDP-based methods.