Quadratic programming

Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

The quadratic programming problem can be formulated as:

Assume x belongs to $\mathbb {R} ^{n}$ space. The n×n matrix Q is symmetric, and c is any n×1 vector.

Minimize (with respect to x)

$f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x}$

Subject to one or more constraints of the form:

$A\mathbf {x} \leq \mathbf {b}$ (inequality constraint)

$E\mathbf {x} =\mathbf {d}$ (equality constraint)

where $\mathbf {x} ^{T}$ indicates the vector transpose of $\mathbf {x}$. The notation $Ax\leq b$ means that every entry of the vector Ax is less than or equal to the corresponding entry of the vector $\mathbf {b}$.

If $Q\;$ is a positive semidefinite matrix, then $f(\mathbf {x} )$ is a convex function. In this case the quadratic program has a global minimizer if there exists at least one vector x satisfying the constraints and $f(\mathbf {x} )$ is bounded below on the feasible region. If the matrix Q is positive definite then this global minimizer is unique. If $Q\;$ is zero, then the problem becomes a linear program. From optimization theory, a necessary condition for a point $\mathbf {x}$ to be a global minimizer is for it to satisfy the Karush–Kuhn–Tucker conditions. These conditions are also sufficient when $f(\mathbf {x} )$ is convex.

Solution methods

If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, a variety of methods for solving the QP are commonly used, including

• interior point
• active set
• conjugate gradient

Convex quadratic programming is a special case of the more general field of convex optimization.

The dual

The dual of a QP is also a QP. To see that let us focus on the case where $c=0$ and Q is positive definite. We write the Lagrangian

$L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b)$

To calculate the dual function $g(\lambda )$, defined as $g(\lambda )=\inf _{x}L(x,\lambda )$ we find the infimum of $L$, using $\nabla _{x}L(x,\lambda )=0$:

$x*=-Q^{-1}A^{T}\lambda$, hence the dual function is

$g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -b^{T}\lambda$

hence the dual of the QP is

maximize :$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -b^{T}\lambda$

subject to :$\lambda \geqslant 0$

Complexity

For positive definite Q, the ellipsoid method solves the problem in polynomial time. If, on the other hand, Q is indefinite, then the problem is NP-hard. In fact, even if Q has only one negative eigenvalue, the problem is NP-hard.

Software packages that include QP solvers

1. Free and opensource, with OSI-Approved licenses

Name	License	Brief info
CVXOPT	GPL	source language: C, Python; API: Python
OpenOpt	BSD	universal cross-platform Python-written numerical optimization framework; see its QP page and full list of problems
OOQP	non-commercial	C++, interior point algorithm implementation by Gertz and Wright
QuadProg	GPL2	source language: R (a port from S), algorithm of Goldfarb and Idnani (1982, 1983)
QuadProg++	LGPL	C++, algorithm of Goldfarb and Idnani (1982, 1983)
uQuadProg	GPLv2+	a port of QuadProg++ that uses BLAS
ROOT	LGPL	source language: C++

2. Commercial

Name
AIMMS Optimization Modeling, the AIMMS software
AMPL Modeling Language AMPL (free for students for problems with up to 300 variables and 300 constraints)
APMonitor Modeling Language trial with up to 10,000,000 variables
Optimization Toolbox MATLAB
CPLEX (convex problems only)
IMSL Numerical Libraries
GAMS, see also GAMS
MOSEK (convex problems only)
The Galahad library (free for academic) features solvers for nonconvex quadratic programs
MINQ Matlab program
Linear and Quadratic Programming Solver in CGAL, the Computational Geometry Algorithms Library

References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP2, pg.245.

See also

• Linear programming
• Support vector machine

External links

• A page about QP
• NEOS guide to QP