OSQP: an operator splitting solver for quadratic programs

By Bartolomeo Stellato, Goran Banjac, Paul J. Goulart, Alberto Bemporad, Stephen P. Boyd. Mathematical Programming Computation, 2017

1,567 citations recorded by the source corpus.

We present a general-purpose solver for convex quadratic programs based on the alternating direction method of multipliers, employing a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix at almost every iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. It can be configured to be division-free once an initial matrix factorization is carried out, making it suitable for real-time applications in embedded systems. In addition, our technique is the first operator splitting method for quadratic programs able to reliably detect primal and dual infeasible problems from the algorithm iterates. The method also supports factorization caching and warm starting, making it particularly efficient when solving parametrized problems arising in finance, control, and machine learning. Our open-source C implementation OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. It is typically ten times faster than competing interior-point methods, and sometimes much more when factorization caching or warm start is used. OSQP has already shown a large impact with tens of thousands of users both in academia and in large corporations.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/0d21f8df95227ef79d8efd2160ff103c6608592f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

HPIPM: a high-performance quadratic programming framework for model predictive control (2020, methodology): “The QP solution times are in Figure 2 for the solvers HPIPM ( speed mode; OCP QP solver for the fully sparse or partially condensed QP; dense QP solver for the condensed QP), OSQP (sparse solver for the fully sparse or partially condensed QP) and qpOASES (for the condensed QP).”
Machine Learning Basics (2021, background): “A few examples of available QP solvers are: qpOASES11, osqp [Stellato et al. 2017]12, GUROBI13, and MOSEK14.”
Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem (2020, methodology): “This limitation, and the myriad of real-world applications with quadratic objectives, has inspired the development of ﬁrst-order ADMM based solvers that tackle the quadratic objective directly [59, 68, 26].”
Under review as a conference paper at ICLR 2020 3 L INEAR INEQUALITY CONSTRAINTS FOR DEEP LEARNING MODELS We consider a generic L layer neural network (2019, methodology): “We used OSQP (Stellato et al., 2017) as an efficient solver to compute orthogonal projections.”
ContactNets: Learning of Discontinuous Contact Dynamics with Smooth, Implicit Representations (2020, methodology): “Parameters are optimized using the loss (16), and osqpth [32, 34] is used to compute its gradient.”
Differentiable Convex Optimization Layers (2019, methodology): “For example, one might use OSQP [69] to solve QPs, or gradient-based methods like L-BFGS [54] or SAGA [28] for empirical risk minimization.”
Geometrically Constrained Trajectory Optimization for Multicopters (2021, positive): “Mellinger’s scheme is implemented using OSQP [61].”
Learning Binary Trees via Sparse Relaxation (2020, methodology): “We compare its solving time with the time needed by the popular convex optimization framework Cvxpy (Diamond & Boyd, 2016; Agrawal et al., 2018) to solve Problem 3 with OSQP solver (Stellato et al., 2020) 4 .”