OSQP: an operator splitting solver for quadratic programs
- PDF / 799,597 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 192 Views
OSQP: an operator splitting solver for quadratic programs Bartolomeo Stellato1 · Goran Banjac2 · Paul Goulart3 · Alberto Bemporad4 · Stephen Boyd5 Received: 7 January 2018 / Accepted: 5 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract 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. Keywords Optimization · Quadratic programming · Operator splitting · First-order methods Mathematics Subject Classification 90C20 · 65K05 · 65K10 · 90C25 · 90C06 · 90C46 · 90C90
This work was supported by the People Programme (Marie Curie Actions) of the European Union Seventh Framework Programme (FP7/2007–2013) under REA Grant agreement No. 607957 (TEMPO).
B
Bartolomeo Stellato [email protected]
Extended author information available on the last page of the article
123
B. Stellato et al.
1 Introduction 1.1 The problem Consider the following optimization problem minimize subject to
(1/2)x T P x + q T x Ax ∈ C,
(1)
where x ∈ Rn is the decision variable. The objective function is defined by a positive semidefinite matrix P ∈ Sn+ and a vector q ∈ Rn , and the constraints by a matrix A ∈ Rm×n and a nonempty, closed and convex set C ⊆ Rm . We will refer to it as general (convex) quadratic program. If the set C takes the form C = [l, u] = z ∈ Rm | li ≤ z i ≤ u i , i = 1, . . . , m , with li ∈ {−∞} ∪ R and u i ∈ R ∪ {+∞}, we can write problem (1) as minimize subject to
(1/2)x T P x + q T x l ≤ Ax ≤ u,
(2)
which we will refer to as a quadratic program (QP). Linear equality constraints can be encoded in this way by setting li = u i for some or all of the elements in (l, u). Note that any linear pr
Data Loading...
