University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Fast ADMM for Semidefinite Programs with Chordal Sparsity

Fast ADMM for Semidefinite Programs with Chordal Sparsity

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

  • UserYang Zheng, Balliol College, University of Oxford
  • ClockThursday 02 February 2017, 12:00-13:00
  • HouseUniversity 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, 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.