Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials
For researchers in polynomial optimization and control, this provides a new relaxation that balances conservatism and computational cost for sparse problems.
The paper introduces sparse sum-of-squares (SSOS) optimization as a bridge between DSOS/SDSOS and SOS optimization for sparse polynomials, proving that SSOS strictly contains DSOS/SDSOS and is less conservative. Numerical results show SSOS can be faster than DSOS/SDSOS despite solving semidefinite programs.
Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. We investigate the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. When applicable, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.