Imperial College London
Portrait Picture

DrAndrewWynn

Faculty of Engineering, Department of Aeronautics

Reader in Control and Optimization
 
 
 
//

Contact

 

+44 (0)20 7594 5047a.wynn Website

 
 
//

Location

 

340City and Guilds BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Zheng:2020:10.1007/s10107-019-01366-3,
author = {Zheng, Y and Fantuzzi, G and Papachristodoulou, A and Goulart, P and Wynn, A},
doi = {10.1007/s10107-019-01366-3},
journal = {Mathematical Programming},
pages = {489--532},
title = {Chordal decomposition in operator-splitting methods for sparse semidefinite programs},
url = {http://dx.doi.org/10.1007/s10107-019-01366-3},
volume = {180},
year = {2020}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Zheng,Y
AU  - Fantuzzi,G
AU  - Papachristodoulou,A
AU  - Goulart,P
AU  - Wynn,A
DO  - 10.1007/s10107-019-01366-3
EP  - 532
PY  - 2020///
SN  - 0025-5610
SP  - 489
TI  - Chordal decomposition in operator-splitting methods for sparse semidefinite programs
T2  - Mathematical Programming
UR  - http://dx.doi.org/10.1007/s10107-019-01366-3
UR  - https://link.springer.com/article/10.1007/s10107-019-01366-3
UR  - http://hdl.handle.net/10044/1/68981
VL  - 180
ER  -
Download