This article's use of external links may not follow Wikipedia's policies or guidelines. Please improve this article by removing excessive or inappropriate external links, and converting useful links where appropriate into footnote references. (November 2011)

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.

Problem formulation [edit]

The quadratic programming problem can be formulated as:^[1]

Assume x belongs to space. Both x and c are column vectors with n elements (n×1 matrices), and Q is a symmetric n×n matrix.

Minimize (with respect to x)

Subject to one or more constraints of the form:

(inequality constraint)

(equality constraint)

where indicates the vector transpose of . The notation means that every entry of the vector is less than or equal to the corresponding entry of the vector .

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

Solution methods [edit]

For general problems a variety of methods are commonly used, including

• interior point,
• active set,^[2]
• augmented Lagrangian,^[3]
• conjugate gradient,
• gradient projection,
• extensions of the simplex algorithm.^[2]

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

Equality constraints [edit]

Quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear. By using Lagrange multipliers and seeking the extremum of the Lagrangian, it may be readily shown that the solution to the equality constrained problem is given by the linear system:

where is a set of Lagrange multipliers which come out of the solution alongside .

The easiest means of approaching this system is direct solution (for example, LU factorization), which for small problems is very practical. For large problems, the system poses some unusual difficulties, most notably that problem is never positive definite (even if is), making it potentially very difficult to find a good numeric approach, and there are many approaches to choose from dependent on the problem.^[4]

If the constraints don't couple the variables too tightly, a relatively simple attack is to change the variables so that constraints are unconditionally satisfied. For example, suppose (generalizing to nonzero is straightforward). Looking at the constraint equations:

introduce a new variable defined by

where has dimension of minus the number of constraints. Then

and if is chosen so that the constraint equation will be always satisfied. Finding such entails finding the null space of , which is more or less simple depending on the structure of . Substituting into the quadratic form gives an unconstrained minimization problem:

the solution of which is given by:

Under certain conditions on , the reduced matrix will be positive definite. It's possible to write a variation on the conjugate gradient method which avoids the explicit calculation of .^[5]

Lagrangian duality [edit]

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

Defining the (Lagrangian) dual function , defined as , we find an infimum of , using

hence the dual function is

hence the Lagrangian dual of the QP is

maximize:

subject to: .

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

Complexity [edit]

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

Solvers and scripting (programming) languages [edit]

See also [edit]

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

References [edit]

Notes [edit]

Bibliography [edit]

• 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. MR 1150683. 
• 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.

External links [edit]

• A page about QP
• NEOS Optimization Guide: Quadratic Programming
• Solve an example Quadratic Programming (QP) problem