A clique graph based merging strategy for decomposable SDPs

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 lead...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों: Garstka, M, Cannon, M, Goulart, P
स्वरूप: Conference item
भाषा:English
प्रकाशित: Elsevier 2021
_version_ 1826289459470008320
author Garstka, M
Cannon, M
Goulart, P
author_facet Garstka, M
Cannon, M
Goulart, P
author_sort Garstka, M
collection OXFORD
description 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.
first_indexed 2024-03-07T02:29:12Z
format Conference item
id oxford-uuid:a6a926ff-50e7-4938-83be-c44ca0f735a1
institution University of Oxford
language English
last_indexed 2024-03-07T02:29:12Z
publishDate 2021
publisher Elsevier
record_format dspace
spelling oxford-uuid:a6a926ff-50e7-4938-83be-c44ca0f735a12022-03-27T02:48:52ZA clique graph based merging strategy for decomposable SDPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a6a926ff-50e7-4938-83be-c44ca0f735a1EnglishSymplectic ElementsElsevier2021Garstka, MCannon, MGoulart, PChordal 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.
spellingShingle Garstka, M
Cannon, M
Goulart, P
A clique graph based merging strategy for decomposable SDPs
title A clique graph based merging strategy for decomposable SDPs
title_full A clique graph based merging strategy for decomposable SDPs
title_fullStr A clique graph based merging strategy for decomposable SDPs
title_full_unstemmed A clique graph based merging strategy for decomposable SDPs
title_short A clique graph based merging strategy for decomposable SDPs
title_sort clique graph based merging strategy for decomposable sdps
work_keys_str_mv AT garstkam acliquegraphbasedmergingstrategyfordecomposablesdps
AT cannonm acliquegraphbasedmergingstrategyfordecomposablesdps
AT goulartp acliquegraphbasedmergingstrategyfordecomposablesdps
AT garstkam cliquegraphbasedmergingstrategyfordecomposablesdps
AT cannonm cliquegraphbasedmergingstrategyfordecomposablesdps
AT goulartp cliquegraphbasedmergingstrategyfordecomposablesdps