Quadratic programming

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

The quadratic programming problem can be formulated like this:

Assume x belongs to $\mathbb {R} ^{n}$ space. The n×n matrix E is symmetric, and h is any n×1 vector.

Minimize (with respect to x)

f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }E\mathbf {x} +\mathbf {h} ^{\mathrm {T} }\mathbf {x}

(Here $\mathbf {v} ^{\mathrm {T} }$ indicates the matrix transpose of v.)

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

Ax ≤ b (inequality constraint)
Cx = d (equality constraint)

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 LOQO. Active set methods are also commonly used.

References

. ISBN 0716710455. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) A6: MP2, pg.245.
. ISBN 0387987932. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) , pg.441.

External links

AIMMS Optimization Modeling — include quadratic programming in industry solutions (free trial license available);

(free trial license available);

This computing article is a stub. You can help Wikipedia by expanding it.