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

The quadratic programming problem can be formulated like this:

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

Minimize (with respect to x)

$f(\backslash mathbf\{x\})\; =\; \backslash frac\{1\}\{2\}\; \backslash mathbf\{x\}^\{\backslash mathrm\{T\}\}\; Q\backslash mathbf\{x\}\; +\; \backslash mathbf\{c\}^\{\backslash mathrm\{T\}\}\; \backslash mathbf\{x\}$

(Here $\backslash mathbf\{v\}^\{\backslash 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. Ex = d (equality constraint)

If Q is positive definite, then f(x) is a convex function and constraints are linear functions. We know 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, as well as Conjugate gradient method with projection.

Complexity

---

For positive-definite Q, the ellipsoid algorithm solves the problem in polynomial time. If Q has at least one negative eigenvalue, the problem is NP-hard.

References

---

• A6: MP2, pg.245.
• , pg.441.
• Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.

External links

---

• A page about QP
• NEOS guide to QP

Software

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

Optimization

Kvadratické programování