Metraipolis › archive › dc_bba2d5fd295b

McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints — arXiv:2610.01503

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.01503
License (as archived)
CC0-1.0
Archived
2026-10-06T16:00:58.574Z
SHA-256 of the archived text
104f2558b8288276f7abe314ab5179099864bc6dd41615287cc933d12f2abaf2
Stable URL of this page
https://metraipolis.com/documento/dc_bba2d5fd295b

How to cite

McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints — arXiv:2610.01503 — arXiv (en), https://arxiv.org/abs/2610.01503 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bba2d5fd295b (Metraipolis archive dc_bba2d5fd295b, sha256 104f2558b8288276f7abe314ab5179099864bc6dd41615287cc933d12f2abaf2)
BibTeX
@misc{dcbba2d5fd295b,
  title = {McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints — arXiv:2610.01503},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.01503},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bba2d5fd295b; sha256 104f2558b8288276f7abe314ab5179099864bc6dd41615287cc933d12f2abaf2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01503. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-02 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.01503 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:14:57.970Z dalla pagina https://arxiv.org/catchup/math.OC/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).