Decomposition methods for large-scale semidefinite programs with chordal aggregate sparsity and partial orthogonality

Zheng Y, Fantuzzi G, Papachristodoulou A (2018)

Publication Type: Book chapter / Article in edited volumes

Publication year: 2018

Journal

Lecture Notes in Mathematics Springer Verlag Kg

Publisher: Springer Verlag

Series: Lecture Notes in Mathematics

Book Volume: 2227

Pages Range: 33-55

DOI: 10.1007/978-3-319-97478-1_3

Abstract

Many semidefinite programs (SDPs) arising in practical applications have useful structural properties that can be exploited at the algorithmic level. In this chapter, we review two decomposition frameworks for large-scale SDPs characterized by either chordal aggregate sparsity or partial orthogonality. Chordal aggregate sparsity allows one to decompose the positive semidefinite matrix variable in the SDP, while partial orthogonality enables the decomposition of the affine constraints. The decomposition frameworks are particularly suitable for the application of first-order algorithms. We describe how the decomposition strategies enable one to speed up the iterations of a first-order algorithm, based on the alternating direction method of multipliers, for the solution of the homogeneous self-dual embedding of a primal-dual pair of SDPs. Precisely, we give an overview of two structure-exploiting algorithms for semidefinite programming, which have been implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate that the decomposition methods described in this chapter promise significant computational gains.

Authors with CRIS profile

Giovanni Fantuzzi

Involved external institutions

University of Oxford GB United Kingdom (GB) Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Zheng, Y., Fantuzzi, G., & Papachristodoulou, A. (2018). Decomposition methods for large-scale semidefinite programs with chordal aggregate sparsity and partial orthogonality. In (pp. 33-55). Springer Verlag.

MLA:

Zheng, Yang, Giovanni Fantuzzi, and Antonis Papachristodoulou. "Decomposition methods for large-scale semidefinite programs with chordal aggregate sparsity and partial orthogonality." Springer Verlag, 2018. 33-55.

BibTeX: Download