Fast ADMM for Semidefinite Programs with Chordal Sparsity

Yang Zheng, University of Oxford


Semidefinite programs (SDPs) are convex optimization problems over the cone of positive semidefinite matrices, which have found applications in a wide range of fields. Small and medium-sized SDPs can be solved up to arbitrary precision in polynomial time using interior-point methods. For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability.

In this talk, I will introduce efficient first-order methods to exploit chordal sparsity in SDPs based on the alternating direction method of multipliers (ADMM). Chordal sparsity in SDPs allows us to decompose the positive semidefinite constraint into a set of smaller, coupled semidefinite constraints, a process known as chordal decomposition. I will show that ADMM and chordal decomposition can be combined to solve sparse SDPs in either primal or dual form, or using a homogeneous self-dual embedding. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, and a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in the open-source MATLAB solver CDCS (Cone Decomposition Conic Solver, Numerical experiments on large-scale sparse problems in SDPLIB show speedups compared to some state-of-the-art software packages.

This is joint work with Giovanni Fantuzzi (Imperial College London), Antonis Papachristodoulou (University of Oxford), Paul Goulart (University of Oxford) and Andrew Wynn (Imperial College London).