Chordal Decomposition in Sparse Semidefinite Optimization and Sum-of-Squares (SOS) Optimization

Thursday, July 12, 2018 - 3:00pm

Event Calendar Category

Other LIDS Events

Speaker Name

Yang Zheng


Oxford University

Building and Room Number



Semidefinite optimization is a type of convex optimization problems over the cone of positive semidefinite (PSD) matrices, while 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. However, 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 of this talk, I will apply this fact to reformulate a sparse semidefinite program (SDP) into an equivalent SDP with smaller PSD constraints. Then, I will discuss how operator-splitting methods can be used to solve the decomposed SDPs efficiently. The resulting algorithms have been implemented in the open-source solver CDCS. In the second part of this talk, I will extend the decomposition result on SDPs to SOS optimization with polynomial constraints. The relationship between the decomposition of SOS optimization and the DSOS/SDSOS techniques (Ahmadi and Majumdar, 2017) will be explored, revealing a practical way to bridge the gap between SOS optimization and DSOS/SDSOS optimization for sparse problem instances.


Yang Zheng received his B.E. and M.S. degrees from Tsinghua University, Beijing, China, in 2013 and 2015, respectively. He is currently working toward the Ph.D. degree under the supervision of Prof. Antonis Papachristodoulou in the Department of Engineering Science, University of Oxford, United Kingdom. His research interests include distributed control of dynamical system over networks, exploiting sparsity in large-scale semidefinite optimization and sum-of-squares (SOS) optimization, with applications to intelligent transportation systems.

Mr. Zheng received the Best Student Paper Award at the 17th IEEE International Conference on Intelligent Transportation Systems in 2014, and the Best Paper Award at the 14th Intelligent Transportation Systems Asia-Pacific Forum in 2015. He is a recipient of the National Scholarship, Outstanding Graduate in Tsinghua University, and the Clarendon Scholarship at the University of Oxford. In 2018, he received the ABTA Doctoral Research Award in Engineering Science.