OSQP: An Operator Splitting Solver for Quadratic Programs

OSQP: An Operator Splitting Solver for Quadratic Programs

February 13, 2020 | Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd
OSQP is a general-purpose solver for convex quadratic programs (QPs) based on the alternating direction method of multipliers (ADMM). It employs a novel operator splitting technique that requires solving a quasi-definite linear system with the same coefficient matrix at almost every iteration. The algorithm is robust, requiring no assumptions about the problem data such as positive definiteness of the objective function or linear independence of the constraints. It can be configured to be division-free once an initial matrix factorization is performed, making it suitable for real-time applications in embedded systems. OSQP is the first operator splitting method for QPs that reliably detects primal and dual infeasibility from the algorithm iterates. It supports factorization caching and warm starting, making it efficient for solving parametrized problems in finance, control, and machine learning. The open-source C implementation of OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances. 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 in academia and large corporations. OSQP solves QPs by introducing auxiliary variables and reformulating the problem as an equality-constrained optimization problem. It uses ADMM to solve the problem, which involves solving a linear system at each iteration. The KKT matrix of the linear system is quasi-definite, allowing for efficient solution using direct or indirect methods. The algorithm is able to provide high accuracy solutions by performing solution polishing on the iterates obtained from ADMM. By identifying the active constraints from the final dual variable iterates, an ancillary equality-constrained QP is constructed, whose solution is equivalent to that of the original QP. This ancillary problem is then solved by computing the solution of a single linear system of typically much lower dimensions than the one solved during the ADMM iterations. If the active constraints are identified correctly, the resulting solution has accuracy equal to or even better than interior-point methods. OSQP can be efficiently warm started to reduce the number of iterations. Moreover, if the problem matrices do not change, the quasi-definite system factorization can be reused across multiple solves, greatly improving the computation time. This feature is particularly useful when solving multiple instances of parametric QPs where only a few elements of the problem data change. OSQP is implemented as an open-source C solver that can be compiled to be library-free. It is robust against noisy and unreliable problem data, has a very small code footprint, and is suitable for both embedded and large-scale applications. OSQP has been extensively tested and carefully tuned by solving millions of QPs. It has been benchmarked against state-of-the-art interior-point and active-set solvers over a benchmark library of 1400 problems from 7 different classes and over the hard QPs Maros-Mészáros test set. Numerical results showOSQP is a general-purpose solver for convex quadratic programs (QPs) based on the alternating direction method of multipliers (ADMM). It employs a novel operator splitting technique that requires solving a quasi-definite linear system with the same coefficient matrix at almost every iteration. The algorithm is robust, requiring no assumptions about the problem data such as positive definiteness of the objective function or linear independence of the constraints. It can be configured to be division-free once an initial matrix factorization is performed, making it suitable for real-time applications in embedded systems. OSQP is the first operator splitting method for QPs that reliably detects primal and dual infeasibility from the algorithm iterates. It supports factorization caching and warm starting, making it efficient for solving parametrized problems in finance, control, and machine learning. The open-source C implementation of OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances. 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 in academia and large corporations. OSQP solves QPs by introducing auxiliary variables and reformulating the problem as an equality-constrained optimization problem. It uses ADMM to solve the problem, which involves solving a linear system at each iteration. The KKT matrix of the linear system is quasi-definite, allowing for efficient solution using direct or indirect methods. The algorithm is able to provide high accuracy solutions by performing solution polishing on the iterates obtained from ADMM. By identifying the active constraints from the final dual variable iterates, an ancillary equality-constrained QP is constructed, whose solution is equivalent to that of the original QP. This ancillary problem is then solved by computing the solution of a single linear system of typically much lower dimensions than the one solved during the ADMM iterations. If the active constraints are identified correctly, the resulting solution has accuracy equal to or even better than interior-point methods. OSQP can be efficiently warm started to reduce the number of iterations. Moreover, if the problem matrices do not change, the quasi-definite system factorization can be reused across multiple solves, greatly improving the computation time. This feature is particularly useful when solving multiple instances of parametric QPs where only a few elements of the problem data change. OSQP is implemented as an open-source C solver that can be compiled to be library-free. It is robust against noisy and unreliable problem data, has a very small code footprint, and is suitable for both embedded and large-scale applications. OSQP has been extensively tested and carefully tuned by solving millions of QPs. It has been benchmarked against state-of-the-art interior-point and active-set solvers over a benchmark library of 1400 problems from 7 different classes and over the hard QPs Maros-Mészáros test set. Numerical results show
Reach us at info@study.space
[slides] OSQP%3A an operator splitting solver for quadratic programs | StudySpace