Fast ADMM for semidefinite programs with chordal sparsity

Zheng Y, Papachristodoulou A, Goulart P, Wynn A (2017)

Publication Type: Conference contribution

Publication year: 2017

Journal

Proceedings of the American Control Conference

Publisher: Institute of Electrical and Electronics Engineers Inc.

Pages Range: 3335-3340

Conference Proceedings Title: Proceedings of the American Control Conference

Event location: Seattle, WA US

ISBN: 9781509059928

DOI: 10.23919/ACC.2017.7963462

Abstract

Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages.

Authors with CRIS profile

Giovanni Fantuzzi

Involved external institutions

University of Oxford GB United Kingdom (GB) Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Zheng, Y., Papachristodoulou, A., Goulart, P., & Wynn, A. (2017). Fast ADMM for semidefinite programs with chordal sparsity. In Proceedings of the American Control Conference (pp. 3335-3340). Seattle, WA, US: Institute of Electrical and Electronics Engineers Inc..

MLA:

Zheng, Yang, et al. "Fast ADMM for semidefinite programs with chordal sparsity." Proceedings of the 2017 American Control Conference, ACC 2017, Seattle, WA Institute of Electrical and Electronics Engineers Inc., 2017. 3335-3340.

BibTeX: Download