OSQP: an operator splitting solver for quadratic programs
We present a general purpose solver for 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 in each iteration. Our algorithm is very r...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
IEEE
2018
|
| _version_ | 1797068311275503616 |
|---|---|
| author | Stellato, B Banjac, G Goulart, P Bemporad, A Boyd, S |
| author_facet | Stellato, B Banjac, G Goulart, P Bemporad, A Boyd, S |
| author_sort | Stellato, B |
| collection | OXFORD |
| description | We present a general purpose solver for 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 in each 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 is 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. |
| first_indexed | 2024-03-06T22:08:55Z |
| format | Journal article |
| id | oxford-uuid:51217d43-aff7-4aac-bd21-39fdb9790c0b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:08:55Z |
| publishDate | 2018 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:51217d43-aff7-4aac-bd21-39fdb9790c0b2022-03-26T16:17:39ZOSQP: an operator splitting solver for quadratic programsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:51217d43-aff7-4aac-bd21-39fdb9790c0bEnglishSymplectic Elements at OxfordIEEE2018Stellato, BBanjac, GGoulart, PBemporad, ABoyd, SWe present a general purpose solver for 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 in each 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 is 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. |
| spellingShingle | Stellato, B Banjac, G Goulart, P Bemporad, A Boyd, S 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 |
| work_keys_str_mv | AT stellatob osqpanoperatorsplittingsolverforquadraticprograms AT banjacg osqpanoperatorsplittingsolverforquadraticprograms AT goulartp osqpanoperatorsplittingsolverforquadraticprograms AT bemporada osqpanoperatorsplittingsolverforquadraticprograms AT boyds osqpanoperatorsplittingsolverforquadraticprograms |