Fast ADMM for Semidefinite Programs with Chordal Sparsity

File Description SizeFormat 
1609.06068v3.pdfAccepted version399.26 kBAdobe PDFView/Open
Title: Fast ADMM for Semidefinite Programs with Chordal Sparsity
Authors: Zheng, Y
Fantuzzi, G
Papachristodoulou, A
Goulart, P
Wynn, A
Item Type: Conference Paper
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 the 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.
Issue Date: 1-Jan-2017
Date of Acceptance: 22-Jan-2017
URI: http://hdl.handle.net/10044/1/55095
DOI: https://dx.doi.org/10.23919/ACC.2017.7963462
Publisher: IEEE
Copyright Statement: © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Conference Name: 2017 American Control Conference
Keywords: math.OC
Notes: 6 pages. Codes available from http://github.com/giofantuzzi/CDCS . Accepted in the American Control Conference, 2017 http://ieeexplore.ieee.org/abstract/document/7963462/
Start Date: 2017-05-24
Finish Date: 2017-05-26
Conference Place: Sheraton Seattle Hotel, Seattle, WA, USA
Appears in Collections:Faculty of Engineering
Aeronautics



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

Creative Commonsx