QP Solvers for Python

Unified interface to Quadratic Programming (QP) solvers available in Python.

Installation

To install both the library and a starter set of free QP solvers:

pip install qpsolvers[open_source_solvers]

To only install the library:

pip install qpsolvers

Check out the documentation for Python 2 or Windows instructions.

Usage

The library provides a one-stop shop solve_qp function with a solver keyword argument to select the backend solver. It solves convex quadratic programs in standard form:

$$ \begin{split} \begin{array}{ll} \mbox{minimize} & \frac{1}{2} x^T P x + q^T x \ \mbox{subject to} & G x \leq h \ & A x = b \ & lb \leq x \leq ub \end{array} \end{split} $$

Vector inequalities are taken coordinate by coordinate. For most solvers, the matrix $P$ should be positive definite.

📢 The solver keyword argument is mandatory since v2.0. (In prior versions, a default solver was implicitly selected.) Changes to the API are reported in the Announcements.

Example

To solve a quadratic program, build the matrices that define it and call the solve_qp function:

from numpy import array, dot
from qpsolvers import solve_qp

M = array([[1., 2., 0.], [-8., 3., 2.], [0., 1., 1.]])
P = dot(M.T, M)  # this is a positive definite matrix
q = dot(array([3., 2., 3.]), M)
G = array([[1., 2., 1.], [2., 0., 1.], [-1., 2., -1.]])
h = array([3., 2., -2.])
A = array([1., 1., 1.])
b = array([1.])

x = solve_qp(P, q, G, h, A, b, solver="osqp")
print("QP solution: x = {}".format(x))

This example outputs the solution [0.30769231, -0.69230769, 1.38461538].

Solvers

Frequently Asked Questions

• Can I print the list of solvers available on my machine?
  • Absolutely: print(qpsolvers.available_solvers)
• Is it possible to solve a least squares rather than a quadratic program?
  • Yes, there is also a solve_ls function.
• I have a squared norm in my cost function, how can I apply a QP solver to my problem?
  • You can cast squared norms to QP matrices and feed the result to solve_qp.
• I have a non-convex quadratic program. Is there a solver I can use?
  • Unfortunately most available QP solvers are designed for convex problems.
  • If your cost matrix P is semi-definite rather than definite, try OSQP.
  • If your problem has concave components, go for a nonlinear solver such as IPOPT e.g. using CasADi.
• I get the following build error on Windows when running pip install qpsolvers.
  • You will need to install the Visual C++ Build Tools to build all package dependencies.
• Can I help?
  • Absolutely! The first step is to install the library and use it. Report any bug in the issue tracker.
  • If you're a developer looking to hack on open source, check out the contribution guidelines for suggestions.

Benchmark

On a dense problem, the performance of all solvers (as measured by IPython's %timeit on an Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz) is:

On a sparse problem with n = 500 optimization variables, these performances become:

On a model predictive control problem for robot locomotion, we get:

Finally, here is a small benchmark of random dense problems (each data point corresponds to an average over 10 runs):

Note that performances of QP solvers largely depend on the problem solved. For instance, MOSEK performs an automatic conversion to Second-Order Cone Programming (SOCP) which the documentation advises bypassing for better performance. Similarly, ECOS reformulates from QP to SOCP and works best on small problems.