Quadratic programming: Difference between revisions

Revision as of 03:41, 17 January 2005

Revision as of 22:14, 5 April 2005

Line 3:

The quadratic programming problem can be formulated like this:

Assume <math>\mathbf{x}</math> belongs to '''R'''<supmath>\mathbb{R}^{n}</supmath> space. The (<math>n x\times n</math>) [[matrix (math)|matrix]] <math>E</math> is [[positive semidefinite]] and <math>\mathbf{h}</math> is any (<math>n x\times 1</math>) vector.

Minimize (with respect to <math>\mathbf{x}</math>)

<center><math>f(x) = 0.5 \mathbf{x'}^{T} E \mathbf{x} + \mathbf{h'}^{T} \mathbf{x}</math></center>

with at least one instance of the following kind of constraints (if there exists an answer then it satisfies these):

(1) <math>A*\mathbf{x} <=\le b</math> (inequality constraint)

(2) <math>C*\mathbf{x } = d</math> (equality contraint)

If <math>E</math> is positive definite then <math>f(\mathbf{x})</math> is a [[convex]] [[function (mathematics)|function]] and constraints are [[linear]] functions. We have from optimization theory that for point <math>\mathbf{x}</math> to be an optimum point it is necessary and sufficient that <math>\mathbf{x}</math> 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.