Sparsity in Sums of Squares of Polynomials

Published: 2003/09/29, Updated: 2005/05/21

Linear, Cone and Semidefinite Programming, Polyhedra polynomial optimization problem, semidefinite programming, sparsity, sums of squares of polynomials Short URL: https://optimization-online.org/?p=9424

Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and SDP (semidefinite programming) relaxation of polynomial optimization problems. We disscuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of squares of sparse polynomials by eliminating redundancy.

Citation

Mathematical Programming Vol. 103 (2005) pp.45-62.