Quadratic programming

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

The quadratic programming problem can be formulated like this:

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

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

${\displaystyle f(x)={1 \over 2}\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) ${\displaystyle A\mathbf {x} \leq b}$  (inequality constraint)
(2) ${\displaystyle C\mathbf {x} =d}$  (equality constraint)

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

• A page about QP
• NEOS guide to QP