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

Understand

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.