Fast ADMM for homogeneous self-dual embedding of sparse SDPs

Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul J. Goulart, Andrew WynnIFAC-PapersOnLine 2017 · DOI

TL;DR

This paper introduces a novel, efficient first-order optimization algorithm based on ADMM for solving a specific type of large-scale semidefinite programming (SDP) problem. By leveraging chordal sparsity and a homogeneous self-dual embedding, their method significantly speeds up computations and can also detect infeasible problems, outperforming existing state-of-the-art solvers on benchmark datasets.

What Problem Does This Paper Address?

Semidefinite programs (SDPs) are powerful tools in various fields like control theory and machine learning. However, solving large-scale SDPs is computationally challenging. While interior-point methods are accurate, they struggle with scalability. Exploiting sparsity in SDPs is a key strategy to improve efficiency. This paper focuses on SDPs with "chordal sparsity," a specific graph-theoretic property that allows large positive semidefinite cones to be decomposed into smaller ones. The challenge is to efficiently solve the homogeneous self-dual embedding formulation of these sparse SDPs, which elegantly handles both feasible and infeasible problems, while also improving computational speed. Existing methods that exploit chordal sparsity often add complexity or don't handle infeasibility.

Methods

The core contribution is an efficient first-order algorithm based on the Alternating Direction Method of Multipliers (ADMM) applied to the homogeneous self-dual embedding of SDPs with chordal sparsity. Here's a breakdown of their approach:

  • Chordal Decomposition: They leverage theorems by Grone et al. and Agler et al. to decompose large semidefinite cones into smaller ones based on the chordal sparsity of the problem's graph. This is a standard technique for sparse SDPs.
  • Homogeneous Self-Dual Embedding: Instead of solving the primal or dual SDP directly, they use the homogeneous self-dual embedding formulation. This approach transforms the problem into a feasibility problem, which inherently handles both primal and dual feasibility/infeasibility. This is a known technique, but its application to chordally sparse SDPs with ADMM is novel.
  • ADMM Adaptation: They adapt the ADMM algorithm proposed by O'Donoghue et al. (2016a) to exploit the specific structure arising from the chordal decomposition and the self-dual embedding.
  • Block Elimination: A key innovation is the use of a series of block eliminations to efficiently solve the linear systems that arise within the ADMM iterations. This significantly reduces the computational cost of the affine projection step, making it comparable to solving the primal or dual problem alone, but with the added benefit of handling infeasibility.

Datasets

The authors evaluated their method on benchmark problems from the SDPLIB library. These include:

  • Small and medium-sized SDPs: Four problems: thetal, theta2, qap5, and qap9.
  • Large-scale sparse SDPs: Four problems: maxG11, maxG32, qpG11, and qpG51.
  • Infeasible SDPs: Two problems: infp1 and infd1.

These datasets are standard for testing SDP solvers and cover a range of sizes and properties.

Key Insights and Ideas

  • Unified Framework for Feasibility and Optimality: The homogeneous self-dual embedding provides a single framework to find optimal solutions for feasible problems and certificates of infeasibility for infeasible ones, which is a significant advantage over methods that only handle one case.
  • Chordal Sparsity as a Computational Lever: The paper demonstrates that chordal sparsity can be effectively exploited not just for interior-point methods but also for first-order methods like ADMM, leading to substantial speedups.
  • Efficient Linear System Solving is Crucial: The bottleneck in ADMM for large-scale problems is often solving linear systems. The paper's clever use of block elimination to simplify these systems is a major technical contribution.
  • Smaller Cones, Faster Projections: By decomposing large semidefinite cones into smaller ones, the conic projection step in ADMM becomes much faster, contributing to the overall efficiency gains.

Key Results

The paper reports significant speedups and improved performance compared to existing methods:

  • Speedups on Large-Scale Sparse SDPs: For the large-scale sparse SDPs tested, their self-dual ADMM method was faster than both the interior-point solver SeDuMi and the first-order solver SCS. For example, on maxG11, their method took 23.9 seconds, while SCS took 114.1 seconds.
  • Handling Infeasible Problems: Their method successfully detected infeasible problems (infp1, infd1), a capability lacking in their previous primal/dual solvers.
  • Comparable Performance on Small/Medium Problems: For smaller problems, their method performed comparably to other solvers.
  • Implementation: The techniques are implemented in the open-source MATLAB solver CDCS (Cone Decomposition Conic Solver), making them accessible to the research community.

Limitations and Future Work

  • MATLAB Implementation: While the results show speedups, the authors note that their MATLAB implementation is compared against a C implementation (SCS). Further optimization might be possible with a C/C++ implementation.
  • Memory for Consensus Constraints: The paper mentions that for problems with a large number of consensus constraints (like qpG51), their approach can still face memory limitations, highlighting a drawback of certain conversion techniques.
  • Future Work: The authors suggest that their work provides a foundation for further research into efficient first-order methods for large-scale conic optimization, particularly those that can leverage problem structure like chordal sparsity. The ability to handle infeasible problems is also a key area for future development in optimization solvers.

Summary updated

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.
BibTeX
@inproceedings{zheng2017fast,
  author = {Yang Zheng and Giovanni Fantuzzi and Antonis Papachristodoulou and Paul J. Goulart and Andrew Wynn},
  title = {{Fast ADMM for homogeneous self-dual embedding of sparse SDPs}},
  booktitle = {IFAC-PapersOnLine},
  year = {2017},
  doi = {10.1016/j.ifacol.2017.08.1569},
}
Figure