Skip to main content

Quadratic programming solvers in Python with a unified API

Project description

QP Solvers for Python

Installation | Documentation | Example | Solvers | FAQ | Benchmark

Build Coverage PyPI version Status

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

Installation

pip install qpsolvers

Check out the documentation for Python 2 or Windows instructions.

Usage

The library provides a one-stop shop solve_qp(P, q, G, h, A, b, lb, ub) function with a solver keyword argument to select the backend solver. It solves convex quadratic programs in standard form:

Quadratic program in standard form

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

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)
print("QP solution: x = {}".format(x))

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

Solvers

The list of supported solvers currently includes:

Solver Keyword Type License Warm-start
CVXOPT cvxopt Dense GPL-3.0 ✔️
ECOS ecos Sparse GPL-3.0 ✖️
Gurobi gurobi Sparse Commercial ✖️
MOSEK mosek Sparse Commercial ✔️
OSQP osqp Sparse Apache-2.0 ✔️
qpOASES qpoases Dense LGPL-2.1
qpSWIFT qpswift Sparse GPL-3.0 ✖️
quadprog quadprog Dense GPL-2.0 ✖️
SCS scs Sparse MIT ✔️

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, qpsolvers also provides a solve_ls function.
  • I have a squared norm in my cost function, how can I apply a QP solver to my problem?
  • 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.

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:

Solver Type Time (ms)
qpswift Dense 0.008
quadprog Dense 0.01
qpoases Dense 0.02
osqp Sparse 0.03
scs Sparse 0.03
ecos Sparse 0.27
cvxopt Dense 0.44
gurobi Sparse 1.74
cvxpy Sparse 5.71
mosek Sparse 7.17

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

Solver Type Time (ms)
osqp Sparse 1
qpswift Dense 2
scs Sparse 4
cvxpy Sparse 11
mosek Sparse 17
ecos Sparse 33
cvxopt Dense 51
gurobi Sparse 221
quadprog Dense 427
qpoases Dense 1560

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

Solver Type Time (ms)
quadprog Dense 0.03
qpswift Dense 0.08
qpoases Dense 0.36
osqp Sparse 0.48
ecos Sparse 0.69
scs Sparse 0.76
cvxopt Dense 2.75
cvxpy Sparse 7.02

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.

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

qpsolvers-1.9.1.tar.gz (47.7 kB view hashes)

Uploaded source

Built Distribution

qpsolvers-1.9.1-py3-none-any.whl (40.6 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page