Chordal decomposition in operator-splitting methods for sparse semidefinite programs
File(s)Zheng2019_Article_ChordalDecompositionInOperator.pdf (1.22 MB)
Published version
Author(s)
Zheng, Y
Fantuzzi, G
Papachristodoulou, A
Goulart, P
Wynn, A
Type
Journal Article
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.
Date Issued
2020-03-01
Date Acceptance
2019-01-22
Citation
Mathematical Programming, 2020, 180 (1-2), pp.489-532
ISSN
0025-5610
Publisher
Springer
Start Page
489
End Page
532
Journal / Book Title
Mathematical Programming
Volume
180
Issue
1-2
Copyright Statement
© 2019 The Author(s). This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Identifier
https://link.springer.com/article/10.1007/s10107-019-01366-3
Grant Number
EP/K503381/1
n/a
EPSRC DTP, award ref. EP/N509486/1
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Software Engineering
Operations Research & Management Science
Mathematics, Applied
Computer Science
Mathematics
Sparse SDPs
Chordal decomposition
Operator-splitting
First-order methods
ALTERNATING DIRECTION METHOD
INTERIOR-POINT METHODS
CONIC OPTIMIZATION
ADMM
Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
0802 Computation Theory and Mathematics
Publication Status
Published
Date Publish Online
2019-02-20