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 the matrix $Q\;$ is positive semidefinite matrix, then $f()$ is a convex function: In this case the quadratic program has a global minimizer if there exists some feasible vector x (satisfying the constraints) and if $f()$ is bounded below on the feasible region. If the matrix Q is positive definite and the problem has a feasible solution, then the global minimizer is unique.

If $Q\;$ is zero, then the problem becomes a linear program.

A related programming problem, quadratically constrained quadratic programming, can be posed by adding quadratic constraints on the variables.

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
• gradient projection
• extensions of the simplex algorithm

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

Lagrangian duality

See also: Lagrange multiplier

The Lagrangian 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 function as

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

Defining the (Lagrangian) dual function $g(\lambda )$, defined as $g(\lambda )=\inf _{x}L(x,\lambda )$, we find an 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 Lagrangian dual of the QP is

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

subject to: $\lambda \geqslant 0$.

Besides the Lagrangian duality theory, there are other duality pairings (e.g. Wolfe, etc.).

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.

Solvers and scripting (programming) languages

Free open-source permissive licenses:

Name	License	Brief info
OpenOpt	BSD	Universal cross-platform numerical optimization framework, see its QP page and other problems involved. Uses NumPy arrays and SciPy sparse matrices.
qp-numpy	BSD	Built around the qld code written by K.Schittkowski of the University of Bayreuth, Germany

Free open-source copyleft (reciprocal) licenses:

Name	License	Brief info
CVXOPT	GPL	General purpose convex optimization solver written in Python

Proprietary:

Name	Brief info
AIMMS
AMPL
CPLEX	Popular solver with an API for several programming languages
EXCEL Solver Function
GAMS
Gurobi
Lingo
MATLAB	A general-purpose and matrix-oriented programming-language for numerical computing. Quadratic programming in MATLAB requires the Optimization Toolbox in addition to the base MATLAB product
Mathematica	A general-purpose programming-language for mathematics, including symbolic and numerical capabilities.
MOSEK	A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python)
OptimJ	Free Java-based Modeling Language for Optimization supporting multiple target solvers and available as an Eclipse plugin
Solver Foundation	A .NET platform for modeling, scheduling, and optimization
TOMLAB
Xpress

References

Bibliography

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc. pp. xxiv+762 pp. ISBN 0-12-192350-9. MR1150683
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP2, pg.245.
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 3-88538-403-5. (Available for download at the website of Professor Katta G. Murty.) MR949214

See also

• Linear programming
• Support vector machine
• Sequential quadratic programming
• Quadratically constrained quadratic programming

External links

• A page about QP
• NEOS guide to QP