Chordal decomposition in operator-splitting methods for sparse semidefinite programs

File Description SizeFormat 
Zheng2019_Article_ChordalDecompositionInOperator.pdfPublished version1.25 MBAdobe PDFView/Open
Title: Chordal decomposition in operator-splitting methods for sparse semidefinite programs
Authors: Zheng, Y
Fantuzzi, G
Papachristodoulou, A
Goulart, P
Wynn, A
Item 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.
Issue Date: 20-Feb-2019
Date of Acceptance: 22-Jan-2019
ISSN: 0025-5610
Publisher: Springer
Journal / Book Title: Mathematical Programming
Copyright Statement: © 2019 The Author(s). This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, 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/Funder: Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/K503381/1
EPSRC DTP, award ref. EP/N509486/1
Keywords: 0102 Applied Mathematics
0103 Numerical and Computational Mathematics
0802 Computation Theory and Mathematics
Operations Research
Publication Status: Published
Open Access location:
Online Publication Date: 2019-02-20
Appears in Collections:Aeronautics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx