publication . Article . Preprint . 2019

COSMO: A conic operator splitting method for convex conic problems

Garstka, Michael; Cannon, Mark; Goulart, Paul;
Open Access
  • Published: 30 Jan 2019
  • Country: United Kingdom
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 spa...
Subjects
free text keywords: Mathematics - Optimization and Control

[Pow69] [Roc70] [Roc76] [Rui01] [Ste+18] [Stu99] N. Parikh, S. Boyd, et al. “Proximal algorithms”. In: Foundations and Trends R in Optimization 1.3 (2014), pp. 127-239.

M. J. Powell. “A method for nonlinear constraints in minimization problems”. In: Optimization (1969), pp. 283-298.

R. T. Rockafellar. Convex analysis. Princeton University Press, 1970.

R. T. Rockafellar. “Monotone operators and the proximal point algorithm”. In: SIAM Journal on Control and Optimization 14.5 (1976), pp. 877-898. [OpenAIRE]

Tech. rep. Rutherford Appleton Laboratory, 2001.

B. Stellato et al. “OSQP: An Operator Splitting Solver for Quadratic Programs”. In: ArXiv e-prints (Jan. 2018). arXiv: 1711.08013 [math.OC]. URL: https://arxiv.org/ abs/1711.08013.

J. F. Sturm. “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones”. In: Optimization Methods and Software 11.1-4 (1999), pp. 625-653.

K. Toh, M. J. Todd, and R. H. Tu¨ tu¨ nc u¨. “SDPT3 - A MATLAB software package for semidefinite programming, version 1.3”. In: Optimization Methods and Software 11.1-4 (1999), pp. 545-581.

L. Vandenberghe, M. S. Andersen, et al. “Chordal graphs and semidefinite optimization”. In: Foundations and Trends R in Optimization 1.4 (2015), pp. 241-433.

R. J. Vanderbei. “Symmetric Quasidefinite Matrices”. In: SIAM Journal on Optimization 5.1 (1995), pp. 100-113.

S. Wright and J. Nocedal. “Numerical optimization”. In: Springer Science 35 (1999).

P. Wolfe. “The simplex method for quadratic programming”. In: Econometrica: Journal of the Econometric Society (1959), pp. 382-398. [OpenAIRE]

S. J. Wright. Primal-dual interior-point methods. Vol. 54. Society for Industrial and Applied Mathematics, 1997.

Y. Zheng et al. “Chordal decomposition in operator-splitting methods for sparse semidefinite programs”. In: ArXiv e-prints (2017). arXiv: 1707 . 05058 [math.OC]. URL: https://arxiv.org/abs/1707.05058.

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 spa...
Subjects
free text keywords: Mathematics - Optimization and Control

[Pow69] [Roc70] [Roc76] [Rui01] [Ste+18] [Stu99] N. Parikh, S. Boyd, et al. “Proximal algorithms”. In: Foundations and Trends R in Optimization 1.3 (2014), pp. 127-239.

M. J. Powell. “A method for nonlinear constraints in minimization problems”. In: Optimization (1969), pp. 283-298.

R. T. Rockafellar. Convex analysis. Princeton University Press, 1970.

R. T. Rockafellar. “Monotone operators and the proximal point algorithm”. In: SIAM Journal on Control and Optimization 14.5 (1976), pp. 877-898. [OpenAIRE]

Tech. rep. Rutherford Appleton Laboratory, 2001.

B. Stellato et al. “OSQP: An Operator Splitting Solver for Quadratic Programs”. In: ArXiv e-prints (Jan. 2018). arXiv: 1711.08013 [math.OC]. URL: https://arxiv.org/ abs/1711.08013.

J. F. Sturm. “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones”. In: Optimization Methods and Software 11.1-4 (1999), pp. 625-653.

K. Toh, M. J. Todd, and R. H. Tu¨ tu¨ nc u¨. “SDPT3 - A MATLAB software package for semidefinite programming, version 1.3”. In: Optimization Methods and Software 11.1-4 (1999), pp. 545-581.

L. Vandenberghe, M. S. Andersen, et al. “Chordal graphs and semidefinite optimization”. In: Foundations and Trends R in Optimization 1.4 (2015), pp. 241-433.

R. J. Vanderbei. “Symmetric Quasidefinite Matrices”. In: SIAM Journal on Optimization 5.1 (1995), pp. 100-113.

S. Wright and J. Nocedal. “Numerical optimization”. In: Springer Science 35 (1999).

P. Wolfe. “The simplex method for quadratic programming”. In: Econometrica: Journal of the Econometric Society (1959), pp. 382-398. [OpenAIRE]

S. J. Wright. Primal-dual interior-point methods. Vol. 54. Society for Industrial and Applied Mathematics, 1997.

Y. Zheng et al. “Chordal decomposition in operator-splitting methods for sparse semidefinite programs”. In: ArXiv e-prints (2017). arXiv: 1707 . 05058 [math.OC]. URL: https://arxiv.org/abs/1707.05058.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue