Abstract

Semidefinite and sum of squares optimization have found a wide range of applications, including control theory, fluid dynamics, machine learning, and power systems. In theory they can be solved in polynomial time using interior-point methods. However, these methods are only practical for small- to medium- sized problem instances.

For large instances, it is essential to exploit or even impose sparsity and structure within the problem in order to solve the associated programs efficiently. In this talk I will present recent results on the analysis and design of networked systems, where chordal sparsity can be used to decompose the resulting SDPs, and solve an equivalent set of smaller semidefinite constraints. I will also discuss how sparsity and operator-splitting methods can be used to speed up computation of large SDPs and introduce our open-source solver CDCS . Lastly, I will extend the decomposition result on SDPs to SOS optimization with polynomial constraints, revealing a practical way to connect SOS optimization and DSOS /SDSOS optimization for sparse problem instances.