Quadratic programming

From Wikipedia, the free encyclopedia

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:[1]

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}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}

Subject to one or more constraints of the form:

Ax \leq b (inequality constraint)
Ex = d (equality constraint)

where \mathbf{v}^T indicates the vector transpose of \mathbf{v}. 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 b.

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

[edit] 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 semidefinite. We write the Lagrangian

L(x,λ) = (1 / 2)xTQx + λT(Ax − b)

To calculate the dual function g(λ), defined as g(\lambda) = \inf_x L(x,\lambda) we find the infimum of L, using \nabla_x L(x,\lambda)=0:

x * = − Q − 1ATλ, hence the dual function is
g(λ) = − (1 / 2)λTAQ − 1ATλ − bTλ

hence the dual of the QP is

maximize : − (1 / 2)λTAQ − 1ATλ − bTλ

subject to :\lambda \geq 0

[edit] Complexity

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

[edit] References

  1. ^ Nocedal, Jorge & Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, p. 449, ISBN 978-0-387-30303-1 .
  2. ^ 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
  3. ^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
  4. ^ 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.

[edit] See also

[edit] External links

Software packages that include QP solvers