Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.
The quadratic programming problem can be formulated as:
Assume x belongs to space. The n×n matrix Q is symmetric, and c is any n×1 vector.
Minimize (with respect to x)
Subject to one or more constraints of the form:
where indicates the vector transpose of . The notation means that every entry of the vector Ax is less than or equal to the corresponding entry of the vector .
If the matrix is positive semidefinite matrix, then f() is a convex function: In this case the quadratic program has a global minimizer if there exists some feasible vector x (satisfying the constraints) and if f() is bounded below on the feasible region. If the matrix Q is positive definite and the problem has a feasible solution, then the global minimizer is unique.
If is zero, then the problem becomes a linear program.
If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, a variety of methods for solving the QP are commonly used, including
Convex quadratic programming is a special case of the more general field of convex optimization.
Full article ▸