Quadratic programming

This is an old revision of this page, as edited by Miaow Miaow (talk | contribs) at 22:29, 13 September 2005 (+cs: interwiki). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

The quadratic programming problem can be formulated like this:

Assume x belongs to space. The n×n matrix E is positive semidefinite and h is any n×1 vector.

Minimize (with respect to x)

(Here indicates the matrix transpose of v.)

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

  1. Axb (inequality constraint)
  2. Cx = d (equality constraint)

If E is positive definite, then f(x) is a convex function and constraints are linear functions. We have 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.