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 symmetric, 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 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.

Complexity

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

References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0716710455. A6: MP2, pg.245.
• Jorge Nocedal and Stephen J. Wright (1999). Numerical Optimization. Springer. ISBN 0387987932. , 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)