McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints
Abstract
sGS-PADMM [21, 14, 6] is a powerful and versatile class of convergent multi-block ADMM solvers for implementations on moderate-sized linear semidefinite programming (SDP) problems. In this paper, we further enhance this class of algorithms for solving SDP problems by proposing a new multi-clique decomposition approach, allowing substantial improvements in applications on large-scale sparse SDPs (e.g., where n > 1000) with conducive aggregate sparsity patterns. Our SDP decomposition strategy mainly aims to reduce the estimated PSD projection cost after decomposition, in contrast to common decomposition algorithms that are encumbered with minimizing the overlaps between cliques. This feature is made possible by our novel linear-space projection approach that is capable of efficiently processing a large number of overlap constraints via simple averaging steps. For the numerical experiments, we demonstrate the performance of our solver -- named McADMM for Multi-clique ADMM -- on a number of large-scale SDP instances that arise from relaxations of some important quadratically constrained quadratic programming (QCQP) problems. The performance of McADMM is contrasted against other state-of-the-art decomposition-based solvers as well as the non-decomposed sGS-PADMM to highlight our key contributions. We additionally develop a GPU implementation of McADMM and demonstrate that it can substantially accelerate the decomposed solver.
Related
- A Smoothed Augmented Lagrangian Method for Mathematical Programs with Vertical Complementarity Constraints
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
- ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
- Augmented Lagrangian Method for Mathematical Programs with Second-Order Cone Complementarity Constraints
- Clique counts under degree and matching constraints
BibTeX
@misc{lian2026mcadmm,
title = {{McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints}},
author = {Kristo Nugraha Lian and Nehal Ahmed Shaikh and Di Hou and Xingyu Xie and Kim-Chuan Toh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01503},
eprint = {2610.01503},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01503},
}
RIS
TY - UNPB
TI - McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints
AU - Kristo Nugraha Lian
AU - Nehal Ahmed Shaikh
AU - Di Hou
AU - Xingyu Xie
AU - Kim-Chuan Toh
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01503
UR - https://arxiv.org/abs/2610.01503
AB - sGS-PADMM [21, 14, 6] is a powerful and versatile class of convergent multi-block ADMM solvers for implementations on moderate-sized linear semidefinite programming (SDP) problems. In this paper, we further enhance this class of algorithms for solving SDP problems by proposing a new multi-clique decomposition approach, allowing substantial improvements in applications on large-scale sparse SDPs (e.g., where n > 1000) with conducive aggregate sparsity patterns. Our SDP decomposition strategy mainly aims to reduce the estimated PSD projection cost after decomposition, in contrast to common decomposition algorithms that are encumbered with minimizing the overlaps between cliques. This feature is made possible by our novel linear-space projection approach that is capable of efficiently processing a large number of overlap constraints via simple averaging steps. For the numerical experiments, we demonstrate the performance of our solver -- named McADMM for Multi-clique ADMM -- on a number of large-scale SDP instances that arise from relaxations of some important quadratically constrained quadratic programming (QCQP) problems. The performance of McADMM is contrasted against other state-of-the-art decomposition-based solvers as well as the non-decomposed sGS-PADMM to highlight our key contributions. We additionally develop a GPU implementation of McADMM and demonstrate that it can substantially accelerate the decomposed solver.
ER -