Fast ADMM for Semidefinite Programs with Chordal Sparsity

Add to your list(s) Download to your calendar using vCal

• Yang Zheng, Balliol College, University of Oxford
• Thursday 02 February 2017, 12:00-13:00
• University House, 110.

If you have a question about this talk, please contact Sergey Sergeev.

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).

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Optimisation and Numerical Analysis Seminars
• School of Mathematics events
• University House, 110

Note that ex-directory lists are not shown.