Fast ADMM for homogeneous self-dual embedding of sparse SDPs

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.

6 pages; Codes are available from https://github.com/giofantuzzi/CDCS/tree/developer (conic solver CDCS); accepted in the IFAC 2017

References in corpus (1)

• Fast ADMM for Semidefinite Programs with Chordal Sparsity

Cited by in corpus (6)

• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number
• Fast ADMM for sum-of-squares programs using partial orthogonality
• Restart of accelerated first order methods with linear convergence under a quadratic functional growth condition
• Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
• Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations