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 ${\displaystyle \mathbb {R} ^{n}}$ space. The n×n matrix E is positive semidefinite and h is any n×1 vector.

Minimize (with respect to x)

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

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

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

1. Ax ≤ b (inequality constraint)
2. Cx = d (equality constraint)

If E xixi 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.

External links

• A page about QP
• NEOS guide to QP