A clique graph based merging strategy for decomposable SDPs. Issue 2 (2020)

• Record Type: Journal Article
• Authors: Garstka, Michael; Cannon, Mark; Goulart, Paul
• Is Part Of: IFAC-PapersOnLine. Volume 53:Issue 2(2020)
• Page Start: 7355
• Page End: 7361
• Publication Date: 2020
• Subjects: convex optimisation -- semidefinite programming -- chordal decomposition -- clique merging; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2020.12.1255
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: Chordal decomposition techniques are used to reduce large structured positive semidefinite matrix constraints in semidefinite programs (SDPs). The resulting equivalent problem contains multiple smaller constraints on the nonzero blocks (or cliques) of the original problem matrices. This usually leads to a significant reduction in the overall solve time. A further reduction is possible by remerging cliques with significant overlap. The degree of overlap for which this is effective is dependent on the particular solution algorithm and hardware to be employed. We propose a novel clique merging approach that utilizes the clique graph to identify suitable merge candidates and that is suitable for any SDP solver algorithm. We show its performance in combination with a first-order method by comparing it with two existing approaches on selected problems from a benchmark library. Our approach is implemented in the latest version of the conic ADMM-solver COSMO.