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 \preceq b$ (inequality constraint)

E x = 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 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.

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

[edit] The Dual

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 T Q x + λ T (A x - 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 * = - (1 / 2) P - 1 A T λ

, hence the dual function is

g (λ) = - (1 / 4)λ T A P - 1 A T λ - b T λ

hence the dual of the QP is

maximize : $- (1 / 4)λ T A P - 1 A T λ - b T λ$

subject to : $\lambda \succeq 0$

[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.