COSMO: A conic operator splitting method for convex conic problems
Preprint
Abstract
This paper describes the Conic Operator Splitting Method (COSMO) solver, 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 low per-iteration computational cost makes the method particularly efficient for large problems, e.g. semidefinite programs that arise in portfolio optimisation, graph theory, and robust control. Moreover, the solver uses chordal decomposition techniques and a new clique merging algorithm to effectively exploit sparsity in large, structured semidefinite programs. A number of benchmarks against other state-of-the-art solvers for a variety of problems show the effectiveness of our approach. Our Julia implementation is open-source, designed to be extended and customised by the user, and is integrated into the Julia optimisation ecosystem.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex OptimizationJournal of Optimization Theory and Applications, 2019
- Conic Optimization via Operator Splitting and Homogeneous Self-Dual EmbeddingJournal of Optimization Theory and Applications, 2016
- Metric selection in fast dual forward–backward splittingAutomatica, 2015
- Reduced clique graphs of chordal graphsEuropean Journal of Combinatorics, 2012
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completionMathematical Programming, 2010
- Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical resultsMathematical Programming, 2003
- Operations research games: A surveyTOP, 2001
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992
- Positive semidefinite matrices with a given sparsity patternLinear Algebra and its Applications, 1988
- A dual algorithm for the solution of nonlinear variational problems via finite element approximationComputers & Mathematics with Applications, 1976