Quadratic programming

From Free net encyclopedia

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

The quadratic programming problem can be formulated like this:

Assume x belongs to <math>\mathbb{R}^{n}</math> space. The n×n matrix Q is symmetric, and c is any n×1 vector.

Minimize (with respect to x)

<math>f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^{\mathrm{T}} Q\mathbf{x} + \mathbf{c}^{\mathrm{T}} \mathbf{x}</math>

(Here <math>\mathbf{v}^{\mathrm{T}}</math> indicates the matrix transpose of v.)

A quadratic programming problem has at least one of the following kinds of constraints:

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

If Q is positive definite, then f(x) is a convex function and constraints are linear functions. We know from optimization theory that for point x to be an optimum point it is necessary and sufficient that x is a Karush-Kuhn-Tucker (KKT) point.

If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, the most common method of solving a QP is an interior point method, such as LOQO. Active set methods are also commonly used.

[edit]

Complexity

For positive-definite Q, the ellipsoid algorithm solves the problem in polynomial time. If Q has at least one negative eigenvalue, the problem is NP-hard.

[edit]

References

Template:Cite book A6: MP2, pg.245.
Template:Cite book , pg.441.
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]