Conference item
A clique graph based merging strategy for decomposable SDPs
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 407.0KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.ifacol.2020.12.1255
Authors
- Publisher:
- Elsevier
- Journal:
- IFAC-PapersOnLine More from this journal
- Volume:
- 53
- Issue:
- 2
- Pages:
- 7355-7361
- Publication date:
- 2021-04-14
- Acceptance date:
- 2020-02-27
- Event title:
- 21st IFAC World Congress
- Event location:
- Berlin, Germany
- Event website:
- https://www.ifac2020.org/
- Event start date:
- 2020-07-12
- Event end date:
- 2020-07-17
- DOI:
- EISSN:
-
2405-8963
- Language:
-
English
- Keywords:
- Pubs id:
-
1090531
- Local pid:
-
pubs:1090531
- Deposit date:
-
2020-03-02
Terms of use
- Copyright holder:
- Garstka et al.
- Copyright date:
- 2020
- Rights statement:
- Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license.
- Notes:
- This conference paper was presented at the 21st IFAC World Congress in Berlin, Germany, 12-17 July 2020.
If you are the owner of this record, you can report an update to it here: Report update to this record