Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Quadratic programming

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

The quadratic programming problem can be formulated like this:

Assume $\mathbf{x}$ belongs to $\mathbb{R}^{n}$ space. The ( $n \times n$ ) matrix $E$ is positive semidefinite and $\mathbf{h}$ is any ( $n \times 1$ ) vector.

Minimize (with respect to $\mathbf{x}$ )

$f(x) = 0.5 \mathbf{x}^{T} E \mathbf{x} + \mathbf{h}^{T} \mathbf{x}$

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

(1)   (inequality constraint)
(2)   (equality contraint)

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

External links

Categories: Optimization

Last updated: 10-24-2005 18:30:55

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects