Factorizing sum-of-squares polynomials

Abstract

Determining whether or notapolynomialisnonnegative is a fundamental problemwithapplications in var ious fields of mathematics and optimization. A popular relaxation technique is to write the polynomial as a sum-of-squares polynomial, since squared polynomials are automatically nonnegative. Finding such a de composition can be reformulated as a semidefinite program, which can then be solved using interior point methods. However, due to the scalability for large semidefinite programs, we explored different methods to f ind a sum-of-squares decomposition, specifically a neural network and the Burer-Monteiro approach for quartics (homogeneous polynomials of degree 4). The neural network outputs a sum-of-squares polynomial by construction, and the Burer-Monteiro ap proach rewrites the semidefinite program by a low-rank decomposition. A special case of univariate polyno mialswasstudiedaswellforBurer-Monteiro. Forbothapproaches,thegradientwasalsocalculatedmanually. The experiments showed that the univariate polynomials followed the theory and converged for a very low rank. After multiple tests, Burer-Monteiro seemed to converge faster in both the number of iterations and in time. Automatic differentiation outperformed manual differentiation, and overparameterization led to faster convergence. However, all tests were performed for polynomials with at most ten variables, and the only method used without parameter optimization was LBFGS, which influences the results. For future research, one can look at different optimizers and higher-degree polynomials in more variables