Semidefinite and sum-of-squares (SOS) optimization are two types of convex optimization problems, which have found a wide range of applications in control theory, fluid dynamics, machine learning, and power systems. They can be solved in polynomial-time using interior-point methods in theory, but these methods are only practical for small- to medium-sized instances. In this talk, I will introduce matrix decomposition methods for semidefinite and SOS optimization, which scale more favorably to large-scale problem instances.

In the first part, the speaker will apply chordal decomposition 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, the speaker 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. They allow for much more efficient computations for sparse problems. This talk is based on our work: https://arxiv.org/abs/1707.05058, and https://arxiv.org/abs/2007.11410

Zoom Link:  https://argonne.zoomgov.com/j/1614519020

See all upcoming talks at http://wordpress.cels.anl.gov/lans-seminars/