Quadratic programming: Difference between revisions

Revision as of 07:17, 20 June 2005

Revision as of 23:10, 22 June 2005

Line 3:

The quadratic programming problem can be formulated like this:

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

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

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

<center>(Here <math>f(x) = {1 \over 2} \mathbf{xv}^{T} E \mathbf{x} + \mathbf{h}^mathrm{T} \mathbf{x}</math></center> indicates the matrix [[transpose]] of '''v'''.)

withA quadratic programming problem has at least one instance of the following kindkinds 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 constraint)

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.

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

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

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.

== External links ==

* [http://www.numerical.rl.ac.uk/qp/qp.html A page about QP]

* [http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/qprog NEOS guide to QP]

{{compcompu-stub}}

[[Category:Optimization]]