Fast ADMM for Semidefinite Programs with Chordal Sparsity

Abstract:

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, https://github.com/OxfordControl/CDCS). 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).