From Wikipedia, the free encyclopedia

Quadratic programming (QP) is a special type of mathematical optimization problem.

The quadratic programming problem can be formulated as:

Assume x belongs to space. The n×n matrix Q is symmetric, and c is any n×1 vector.

Minimize (with respect to x)

Subject to one or more constraints of the form:

(inequality constraint)

Ex = d (equality constraint)

where indicates the vector transpose of .

If Q is a positive semidefinite matrix, then f(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(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 x to be a global minimizer is for it to satisfy the Karush-Kuhn-Tucker (KKT) conditions. The KKT conditions are also sufficient when f(x) is convex.

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 and conjugate gradient methods.

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

Contents 1 The Dual 2 Complexity 3 References 4 See also 5 External links

The dual of a QP is also a QP. To see that lets focuse on the case where c = 0 and Q is PSD. We write the Lagrangian

L(x,λ) = x^TQx + λ^T(Ax − b)

To calculate the dual function g(λ), defined as we find the infimum of L, using :

x * = − (1 / 2)P ^{− 1}A^Tλ, hence the dual function is

g(λ) = − (1 / 4)λ^TAP ^{− 1}A^Tλ − b^Tλ

hence the dual of the QP is

maximize : − (1 / 4)λ^TAP ^{− 1}A^Tλ − b^Tλ

subject to :

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

1. ^ Kozlov, M.K.; Tarasov, S.P.; Khachiyan, L.G. "Polynomial solvability of convex quadratic programming," in Sov. Math., Dokl. 20, 1108-1111 (1979). This is a translation from Dokl. Akad. Nauk SSSR 248, 1049-1051 (1979). ISSN: 0197-6788
2. ^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
3. ^ Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.

• 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.
• Jorge Nocedal and Stephen J. Wright (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.  , pg.441.

• Linear programming
• Support vector machine

• A page about QP
• NEOS guide to QP

Software packages that include QP solvers

• AIMMS Optimization Modeling, the AIMMS software
• MOSEK
• QuadProg++ by Luca di Gaspero, freely available and written in C++