##### Department of Mathematics,

University of California San Diego

****************************

### Math 278C - Optimization and Data Science

## Yang Zheng

#### UCSD

## Chordal Graphs, Semidefinite Optimization, and Sum-of-squares Matrices

##### 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 decompose a PSD cone into 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 operator-splitting 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 and https://arxiv.org/abs/2007.11410

Host: Jiawang Nie

### October 27, 2021

### 3:00 PM

Zoom Meeting ID: 991 9807 8858 Password: 278CFA21

****************************