Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials
arXiv:1807.05463 · doi:10.23919/ACC.2019.8814998
Abstract
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.
arXiv comment9 pages, 3 figures
References in corpus (3)
Cited by in corpus (4)
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Bounding extrema over global attractors using polynomial optimisation
- Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization
- Efficient Data Structures for Exploiting Sparsity and Structure in Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS