Quadratic programming

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

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}) = \frac{1}{2} \mathbf{x}' Q\mathbf{x} + \mathbf{c}' \mathbf{x}$

Subject to one or more constraints of the form:

Ax ≤ b (inequality constraint)
Ex = d (equality constraint)

where $\mathbf{v}'$ indicates the vector transpose of $\mathbf{v}$ .

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. 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 and sufficient condition for a point x to be a global minimizer is for it to satisfy the Karush-Kuhn-Tucker (KKT) conditions.

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.

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

1 Complexity
2 References
3 See also
4 External links

[edit] Complexity

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]

[edit] References

^ 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
^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
^ 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.