Fast ADMM for homogeneous self-dual embedding of sparse SDPs

File Description SizeFormat 
1611.01828v2.pdfAccepted version135.2 kBAdobe PDFView/Open
Title: Fast ADMM for homogeneous self-dual embedding of sparse SDPs
Authors: Zheng, Y
Fantuzzi, G
Papachristodoulou, A
Goulart, P
Wynn, A
Item 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.
Issue Date: 18-Oct-2017
Date of Acceptance: 27-Feb-2017
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
Conference Name: 20th IFAC World Congress
Keywords: math.OC
Notes: 6 pages; Codes are available from (conic solver CDCS); accepted in the IFAC 2017
Publication Status: Published
Start Date: 2017-07-09
Finish Date: 2017-07-14
Conference Place: Toulouse, France
Appears in Collections:Faculty of Engineering

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx