Quadratic programming: Difference between revisions

Revision as of 22:29, 14 February 2004

Revision as of 22:43, 14 February 2004

Line 1:

'''Quadratic programming''' (QP) is a special type of mathematical [[optimization (mathematics) | optimization]] problem.

QuadraticThe quadratic programming problem can be formulated like this:

Assume x belongs to '''R'''ⁿ space. The (n x n) [[matrix]] E is [[positive semidefinite]] and h is any (n x 1) vector.

Line 9:

f(x) = 0.5 x' E x + h' x

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

(1) A*x <= b (inequality constraint)

(2) C*x = d (equality contraint)

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 [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]

{{msg:stub}}