Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization

Abstract

Semidefinite programs (SDPs) are standard convex problems that are frequently found in control and optimization applications. Interior-point methods can solve SDPs in polynomial time up to arbitrary accuracy, but scale poorly as the size of matrix variables and the number of constraints increases. To improve scalability, SDPs can be approximated with lower and upper bounds through the use of structured subsets (e.g., diagonally-dominant and scaled-diagonally dominant matrices). Meanwhile, any underlying sparsity or symmetry structure may be leveraged to form an equivalent SDP with smaller positive semidefinite constraints. In this paper, we present a notion of decomposed structured subsets}to approximate an SDP with structured subsets after an equivalent conversion. The lower/upper bounds found by approximation after conversion become tighter than the bounds obtained by approximating the original SDP directly. We apply decomposed structured subsets to semidefinite and sum-of-squares optimization problems with examples of H-infinity norm estimation and constrained polynomial optimization. An existing basis pursuit method is adapted into this framework to iteratively refine bounds.

23 pages, 10 figures, 9 tables

References in corpus (7)

• Symmetry groups, semidefinite programs, and sums of squares
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Symmetry in semidefinite programs
• TSSOS: A Moment-SOS hierarchy that exploits term sparsity
• Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization
• Global Optimization via the Dual SONC Cone and Linear Programming
• A hierarchy of spectral relaxations for polynomial optimization

Cited by in corpus (4)

• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• TSSOS: A Moment-SOS hierarchy that exploits term sparsity
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions