Quadratic programming

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,))
A = array([1., 1., 1.])
b = array([1.])

x = solve_qp(P, q, G, h, A, b)
print(f"QP solution: x = {x}")

This example outputs the solution [0.30769231, -0.69230769,  1.38461538]. The solve_qp() function accepts a solver keyword argument to select the backend solver:

qpsolvers.solve_qp(P, q, G=None, h=None, A=None, b=None, lb=None, ub=None, solver='quadprog', initvals=None, sym_proj=False, verbose=False, **kwargs)

Solve a Quadratic Program defined as:

\[\begin{split}\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}\end{split}\]

using one of the available QP solvers.

Parameters
  • P (Union[ndarray, csc_matrix, spmatrix]) – Symmetric quadratic-cost matrix (most solvers require it to be definite as well).

  • q (Union[ndarray, csc_matrix, spmatrix]) – Quadratic-cost vector.

  • G (Union[ndarray, csc_matrix, spmatrix, None]) – Linear inequality matrix.

  • h (Union[ndarray, csc_matrix, spmatrix, None]) – Linear inequality vector.

  • A (Union[ndarray, csc_matrix, spmatrix, None]) – Linear equality matrix.

  • b (Union[ndarray, csc_matrix, spmatrix, None]) – Linear equality vector.

  • lb (Union[ndarray, csc_matrix, spmatrix, None]) – Lower bound constraint vector.

  • ub (Union[ndarray, csc_matrix, spmatrix, None]) – Upper bound constraint vector.

  • solver (str) – Name of the QP solver, to choose in qpsolvers.available_solvers.

  • initvals (Union[ndarray, csc_matrix, spmatrix, None]) – Vector of initial \(x\) values used to warm-start the solver.

  • sym_proj (bool) – Set to True when the \(P\) matrix provided is not symmetric.

  • verbose (bool) – Set to True to print out extra information.

Return type

Optional[ndarray]

Returns

Optimal solution if found, otherwise None.

Raises

ValueError – If the problem is not correctly defined.

Note

In quadratic programming, the matrix \(P\) should be symmetric. Many solvers (including CVXOPT, OSQP and quadprog) leverage this property and may return unintended results when it is not the case. You can set sym_proj=True to project \(P\) on its symmetric part, at the cost of some computation time.

Notes

Extra keyword arguments given to this function are forwarded to the underlying solvers. For example, OSQP has a setting eps_abs which we can provide by solve_qp(P, q, G, h, solver='osqp', eps_abs=1e-4).

Installed solvers are listed in:

qpsolvers.available_solvers = ['cvxopt', 'cvxpy', 'ecos', 'gurobi', 'mosek', 'osqp', 'qpoases', 'quadprog', 'scs']

Built-in mutable sequence.

If no argument is given, the constructor creates a new empty list. The argument must be an iterable if specified.

See the examples/ folder in the repository for other use cases. For a more general introduction you can also check out this post on quadratic programming in Python.