Fast ADMM for homogeneous self-dual embeddings of sparse SDPs

Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. J. Goulart and A. Wynn

@inproceedings{ZFPetal:2017b,
  author = {Y. Zheng and G. Fantuzzi and A. Papachristodoulou and P. J. Goulart and A. Wynn},
  title = {Fast ADMM for homogeneous self-dual embeddings of sparse SDPs},
  booktitle = {IFAC World Congress},
  year = {2017},
  pages = {8411-8416}
}

We propose an efficient first-order method, based on the alternating directions method of multipliers (ADMM), to solve the the homogeneous self-dual embedding of 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 only 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 it provides 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.