OSQP: an operator splitting solver for quadratic programs
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131868 |
| _version_ | 1811094286724235264 |
|---|---|
| author | Stellato, Bartolomeo Banjac, Goran Goulart, Paul Bemporad, Alberto Boyd, Stephen |
| author_facet | Stellato, Bartolomeo Banjac, Goran Goulart, Paul Bemporad, Alberto Boyd, Stephen |
| author_sort | Stellato, Bartolomeo |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:57:37Z |
| format | Article |
| id | mit-1721.1/131868 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:57:37Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1318682021-09-21T03:08:17Z OSQP: an operator splitting solver for quadratic programs Stellato, Bartolomeo Banjac, Goran Goulart, Paul Bemporad, Alberto Boyd, Stephen 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. 2021-09-20T17:30:43Z 2021-09-20T17:30:43Z 2020-02-20 2020-10-16T03:22:32Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131868 en https://doi.org/10.1007/s12532-020-00179-2 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Stellato, Bartolomeo Banjac, Goran Goulart, Paul Bemporad, Alberto Boyd, Stephen OSQP: an operator splitting solver for quadratic programs |
| title | OSQP: an operator splitting solver for quadratic programs |
| title_full | OSQP: an operator splitting solver for quadratic programs |
| title_fullStr | OSQP: an operator splitting solver for quadratic programs |
| title_full_unstemmed | OSQP: an operator splitting solver for quadratic programs |
| title_short | OSQP: an operator splitting solver for quadratic programs |
| title_sort | osqp an operator splitting solver for quadratic programs |
| url | https://hdl.handle.net/1721.1/131868 |
| work_keys_str_mv | AT stellatobartolomeo osqpanoperatorsplittingsolverforquadraticprograms AT banjacgoran osqpanoperatorsplittingsolverforquadraticprograms AT goulartpaul osqpanoperatorsplittingsolverforquadraticprograms AT bemporadalberto osqpanoperatorsplittingsolverforquadraticprograms AT boydstephen osqpanoperatorsplittingsolverforquadraticprograms |