Quadratic Programming solvers in Python with a unified API
Clone or download

README.md

QP Solvers for Python

Wrapper around Quadratic Programming (QP) solvers in Python, with a unified interface.

Installation

The simplest way to install this module is:

pip install qpsolvers

You can add the --user parameter for a user-only installation. See also the wiki page for advanced installation instructions.

Usage

The function solve_qp(P, q, G, h, A, b) is called with the solver keyword argument to select the backend solver. The quadratic program it solves is, in standard form:

Vector inequalities are taken coordinate by coordinate.

Solvers

The list of supported solvers currently includes:

Example

To solve a quadratic program, simply 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)  # quick way to build a symmetric matrix
q = dot(array([3., 2., 3.]), M).reshape((3,))
G = array([[1., 2., 1.], [2., 0., 1.], [-1., 2., -1.]])
h = array([3., 2., -2.]).reshape((3,))

print "QP solution:", solve_qp(P, q, G, h)

This example outputs the solution [-0.49025721 -1.57755261 -0.66484801].

Performances

On the dense example above, the performance of all solvers (as measured by IPython's %timeit on my machine) is:

Solver Type Time (ms)
quadprog Dense 0.02
qpoases Dense 0.03
osqp Sparse 0.04
cvxopt Dense 0.43
gurobi Sparse 0.84
ecos Sparse 2.61
mosek Sparse 7.17

Meanwhile, on the sparse.py example, these performances become:

Solver Type Time (ms)
osqp Sparse 1
mosek Sparse 17
cvxopt Dense 35
gurobi Sparse 221
quadprog Dense 421
ecos Sparse 638
qpoases Dense 2210

Finally, here are the results on a benchmark of random problems generated with the randomized.py example (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.