Abstract: Semidefinite optimization is a type of convex optimization problems over the cone of positive semidefinite (PSD) matrices, and sum-of-squares (SOS) optimization is another type of convex optimization problems concerned with the cone of SOS polynomials. Both semidefinite and SOS 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, but these methods are only practical for small- to medium-sized problem instances. In this talk, I will introduce decomposition methods for semidefinite optimization and SOS optimization with chordal sparsity, which scale more favorably to large-scale problem instances. It is known that chordal decomposition allows one to equivalently replace a PSD cone with a set of smaller and coupled cones. In the first part, I will apply this fact to reformulate a sparse semidefinite program (SDP) into an equivalent SDP with smaller PSD constraints that is suitable for the application of first-order methods. The resulting algorithms have been implemented in the open-source solver CDCS. In the second part, I will extend the classical chordal decomposition to the case of sparse polynomial matrices that are positive (semi)definite globally or locally on a semi-algebraic set. The extended decomposition results can be viewed as sparsity-exploiting versions of the Hilbert-Artin, Reznick, Putinar, and Putinar-Vasilescu Positivstellensätze.

This talk is based on our work: https://arxiv.org/abs/1707.05058; https://arxiv.org/abs/2007.11410; and https://arxiv.org/abs/2107.02379.