Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

Fast ADMM for homogeneous self-dual embedding of sparse SDPs

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

---

Publication Type: Conference contribution

Publication year: 2017

Journal

Publisher: Elsevier B.V.

Book Volume: 50

Pages Range: 8411-8416

Conference Proceedings Title: IFAC-PapersOnLine

DOI: 10.1016/j.ifacol.2017.08.1569

Abstract

We propose an efficient first-order method, based on the alternating direction method of multipliers (ADMM), to solve the homogeneous self-dual embedding problem for a primal-dual pair of semidefinite programs (SDPs) with chordal sparsity. Using a series of block eliminations, the per-iteration cost of our method is the same as applying a splitting method to the primal or dual alone. Moreover, our approach is more efficient than other first-order methods for generic sparse conic programs since we work with smaller semidefinite cones. In contrast to previous first-order methods that exploit chordal sparsity, our algorithm returns both primal and dual solutions when available, and a certificate of infeasibility otherwise. Our techniques are implemented in the open-source MATLAB solver CDCS. Numerical experiments on three sets of benchmark problems from the library SDPLIB show speed-ups compared to some common state-of-the-art software packages.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., & Wynn, A. (2017). Fast ADMM for homogeneous self-dual embedding of sparse SDPs. In IFAC-PapersOnLine (pp. 8411-8416). Elsevier B.V..

MLA:

Zheng, Yang, et al. "Fast ADMM for homogeneous self-dual embedding of sparse SDPs." Proceedings of the IFAC-PapersOnLine Elsevier B.V., 2017. 8411-8416.

BibTeX: Download