Fast ADMM for homogeneous self-dual embedding of sparse SDPs *. Issue 1 (July 2017)

• Record Type: Journal Article
• Authors: Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew
• Is Part Of: IFAC-PapersOnLine. Volume 50:Issue 1(2017)
• Page Start: 8411
• Page End: 8416
• Publication Date: 2017-07
• Subjects: Convex optimization -- semidefinite programs -- chordal sparsity -- large-scale problems -- first-order methods; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2017.08.1569
• Languages: English
• ISSNs: 2405-8963

Abstract

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.