Fast ADMM for homogeneous self-dual embedding of sparse SDPs
File(s)
Accepted version
Author(s)
Zheng, Yang
Fantuzzi, Giovanni
Papachristodoulou, Antonis
Goulart, Paul
Wynn, Andrew
Type
Conference Paper
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.
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.
Date Issued
2017-10-18
Date Acceptance
2017-02-27
Citation
IFAC Proceedings Volumes (IFAC-PapersOnline), 2017, 50 (1), pp.8411-8416
ISSN
1474-6670
Publisher
Elsevier
Start Page
8411
End Page
8416
Journal / Book Title
IFAC Proceedings Volumes (IFAC-PapersOnline)
Volume
50
Issue
1
Copyright Statement
© 2017, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Identifier
http://arxiv.org/abs/1611.01828v2
Source
20th IFAC World Congress
Subjects
math.OC
math.OC
Notes
6 pages; Codes are available from https://github.com/giofantuzzi/CDCS/tree/developer (conic solver CDCS); accepted in the IFAC 2017
Publication Status
Published
Start Date
2017-07-09
Finish Date
2017-07-14
Coverage Spatial
Toulouse, France