Exploiting Sparsity in Semidefinite and Sum of Squares Programming

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.

BIO: Antonis Papachristodoulou joined the University of Oxford in 2006, where he is currently Professor of Engineering Science and a Tutorial Fellow in Worcester College. Since 2015, he has been EPSRC Fellow and Director of the EPSRC & BBSRC Centre for Doctoral training in Synthetic Biology. He holds an MA/MEng in Electrical and Information Sciences from the University of Cambridge (2000) and a PhD in Control and Dynamical Systems from the California Institute of Technology, with a PhD Minor in Aeronautics (2005). In 2015 he was awarded the European Control Award for his contributions to robustness analysis and applications to networked control systems and systems biology and the O. Hugo Schuck Best Paper Award. He is an IEEE Fellow for contributions to the analysis and design of networked control systems. He serves regularly on Technical Programme Committees for conferences, and was associate editor for Automatica and IEEE Transactions on Automatic Control.

Hosted by: Mihailo Jovanovic