Chordal decomposition in operator-splitting methods for sparse semidefinite programs

Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, Andrew WynnMath. Program 2020 · OpenReview

TL;DR

This paper introduces a novel approach to solve large, sparse Semidefinite Programs (SDPs) by combining chordal decomposition with operator-splitting methods like ADMM. This allows for efficient decomposition of large SDPs into smaller, parallelizable subproblems, leading to significant speedups and the ability to handle previously intractable problems.

What Problem Does This Paper Address?

Semidefinite Programs (SDPs) are powerful optimization tools with applications across many fields, but solving large-scale SDPs has been a significant challenge. Traditional interior-point methods struggle with the computational cost and memory requirements of large, dense positive semidefinite (PSD) constraints. While first-order methods offer a potential solution, they often lack the accuracy or ability to detect infeasibility. This paper tackles the problem of efficiently solving large, sparse SDPs, particularly those with a specific structure called "chordal sparsity," which is common in real-world applications. The goal is to develop algorithms that are both scalable and robust.

Methods

The core innovation lies in the chordal decomposition technique. This method leverages the chordal sparsity of the problem's aggregate sparsity pattern to break down a large PSD constraint into a set of smaller, coupled PSD constraints on submatrices. This decomposition is then combined with the Alternating Direction Method of Multipliers (ADMM), a powerful first-order optimization algorithm.

Key aspects of their method include:

  • Domain-space and Range-space Decomposition: They apply chordal decomposition to both the primal and dual forms of the SDP, creating "decomposed" problems. This involves introducing slack variables to separate conic and affine constraints, making them amenable to ADMM.
  • ADMM Application: ADMM is used to solve these decomposed SDPs. A crucial advantage is that each ADMM iteration involves projections onto small PSD cones (which can be done in parallel) and solving a linear system.
  • Homogeneous Self-Dual Embedding (HSDE): They also formulate and solve the HSDE of the decomposed SDPs. This allows the algorithm to not only find optimal solutions but also to detect infeasible problems and provide certificates of infeasibility, a significant advantage over many other first-order methods.
  • Efficient Linear System Solving: For the HSDE, they exploit the structure of the problem to efficiently solve large linear systems using block eliminations, further enhancing performance.
  • MATLAB Solver CDCS: All proposed algorithms are implemented in an open-source MATLAB solver called CDCS (Cone Decomposition Conic Solver).

Datasets

The paper evaluates their algorithms on several benchmark datasets:

  • SDPLIB: A collection of standard SDP problems, including small dense problems (thetal, theta2), infeasible problems (infdl, infd2), and large sparse problems (maxG11, maxG32, qpG11, qpG51).
  • Nonchordal Sparsity Patterns: Large-scale SDPs with nonchordal sparsity patterns from the University of Florida Sparse Matrix Collection.
  • Random SDPs with Block-Arrow Patterns: Randomly generated SDPs with a specific "block-arrow" sparsity structure to analyze the impact of problem parameters (number of constraints, number of blocks, clique size) on performance.

Key Insights and Ideas

  • Chordal Sparsity is Key: The paper demonstrates that exploiting chordal sparsity is crucial for decomposing large SDPs into manageable subproblems. This structure allows for a more efficient breakdown than general sparsity.
  • ADMM + Chordal Decomposition = Scalability: The combination of chordal decomposition and ADMM is highly effective for large-scale SDPs. The decomposition breaks down the problem into smaller, parallelizable conic projections, while ADMM efficiently handles the resulting structure.
  • Infeasibility Detection is Achievable: By formulating the homogeneous self-dual embedding (HSDE), the authors show that first-order methods can indeed detect infeasible SDPs and provide certificates, a capability often missing in simpler first-order approaches.
  • Structure Exploitation for Linear Systems: The paper highlights how understanding the structure of the linear systems arising in ADMM (especially for the HSDE) can lead to significant computational savings through techniques like block elimination.

Key Results

  • Significant Speedups: Numerical experiments show that their proposed algorithms, implemented in CDCS, are significantly faster than state-of-the-art interior-point solvers (SeDuMi) and other first-order solvers (SCS) on large-scale sparse SDPs. For example, CDCS-hsde achieved speedups of up to 43x over SCS on some problems.
  • Handling Infeasibility: CDCS-hsde successfully detects infeasible problems, a capability not present in the primal/dual ADMM algorithms.
  • Accuracy: The solutions obtained by CDCS are comparable in accuracy to those from high-accuracy solvers, with terminal objective values typically within 0.2% of optimal.
  • Scalability: The computational cost per iteration of CDCS grows more slowly with problem size (especially the number of maximal cliques) compared to solvers that operate on the original, un-decomposed problem.

Limitations and Future Work

  • Sequential Implementation: While many steps can be parallelized, the current implementation of CDCS is sequential. Future work could leverage parallel computing architectures for further speedups.
  • Nonchordal Sparsity: The current framework relies on chordal sparsity. The authors suggest exploring how first-order methods can be extended to handle other types of sparsity and structure, such as those found in SDPs from sum-of-squares relaxations.
  • Parameter Tuning: While CDCS uses a dynamic adaptive penalty strategy, ADMM performance can still be sensitive to problem scaling and parameter choices. Further investigation into parameter selection and scaling strategies is suggested.
  • PSD Completion: The method for recovering primal-dual solutions relies on a maximum determinant completion routine, which may fail if the candidate solution is not strictly positive definite. The authors acknowledge this and plan to integrate more robust completion methods.

Summary updated

Abstract

We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomposed primal- and dual-standard-form SDPs. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. We also formulate the homogeneous self-dual embedding (HSDE) of a primal-dual pair of decomposed SDPs, and extend a recent ADMM-based algorithm to exploit the structure of our HSDE. The resulting HSDE algorithm has the same leading-order computational cost as those for the primal or dual problems only, with the advantage of being able to identify infeasible problems and produce an infeasibility certificate. All algorithms are implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate the computational advantages of the proposed methods compared to common state-of-the-art solvers.
BibTeX
@inproceedings{zheng2020chordal,
  author = {Yang Zheng and Giovanni Fantuzzi and Antonis Papachristodoulou and Paul Goulart and Andrew Wynn},
  title = {{Chordal decomposition in operator-splitting methods for sparse semidefinite programs}},
  booktitle = {Math. Program},
  year = {2020},
  url = {https://openreview.net/forum?id=YrHZLJsMZB},
}
Figure