Quadratic programming: Difference between revisions

Revision as of 11:17, 2 March 2006

Revision as of 07:01, 17 March 2006

Line 3:

The quadratic programming problem can be formulated like this:

Assume '''x''' belongs to <math>\mathbb{R}^{n}</math> space. The ''n''&times;''n'' [[matrix (math)|matrix]] ''EQ'' is symmetric, and '''hc''' is any ''n''&times;1 vector.

Minimize (with respect to '''x''')

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

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

Line 12:

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

# ''A'''''x''' &le; ''b'' (inequality constraint)

# ''CE'''''x''' = ''d'' (equality constraint)

If ''EQ'' is [[positive-definite matrix|positive definite]], then ''f''('''x''') is a [[convex]] [[function (mathematics)|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 [http://www.orfe.princeton.edu/~loqo LOQO]. [[Active set]] methods are also commonly used.

==Complexity==

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

==References==