Fast ADMM for homogeneous self-dual embeddings of sparse SDPs. 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 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.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Eltved, Anders; Dahl, Joachim; Andersen, Martin S.: On the robustness and scalability of semidefinite relaxation for optimal power flow problems (2020)
- Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew: Chordal decomposition in operator-splitting methods for sparse semidefinite programs (2020)
- Fantuzzi, Giovanni; Pershin, Anton; Wynn, Andrew: Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number (2018)