COSMO: A conic operator splitting method for convex conic problems

Michael Garstka, Mark Cannon and Paul Goulart

September 2020.
BibTeX  Preprint  Code 

@inproceedings{GCG:2020b,
  author = {Michael Garstka and Mark Cannon and Paul Goulart},
  title = {COSMO: A conic operator splitting method for convex conic problems},
  year = {2020}
}

This paper describes the Conic Operator Splitting Method (COSMO), an operator splitting algorithm for convex optimisation problems with quadratic objective function and conic constraints. At each step the algorithm alternates between solving a quasi-definite linear system with a constant coefficient matrix and a projection onto convex sets. The solver is able to exploit chordal sparsity in the problem data and to detect infeasible problems. The low per-iteration computational cost makes the method particularly efficient for large problems, e.g. semidefinite programs in portfolio optimisation, graph theory, and robust control. Our Julia implementation is open-source, extensible, integrated into the Julia optimisation ecosystem and performs well on a variety of large convex problem classes.

A clique graph based merging strategy for decomposable SDPs

M. Garstka, M. Cannon and P. J. Goulart

in IFAC World Congress, Berlin, Germany, July 2020.
BibTeX  Preprint  Code 

@inproceedings{GCG:2020,
  author = {M. Garstka and M. Cannon and P. J. Goulart},
  title = {A clique graph based merging strategy for decomposable SDPs},
  booktitle = {IFAC World Congress},
  year = {2020}
}

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. We show its performance by comparing it with two existing methods on selected problems from a benchmark library. Our approach is implemented in the latest version of the conic ADMM-solver COSMO.