Quadratic programming (QP) is the process of solving a special type of mathematical optimization problem—specifically, a (linearly constrained) quadratic optimization problem, that is, the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables. Quadratic programming is a particular type of nonlinear programming.
Contents
Problem formulation
The quadratic programming problem with n variables and m constraints can be formulated as follows. Given:
the objective of quadratic programming is to find an n-dimensional vector x, that will
where xT denotes the vector transpose of
A related programming problem, quadratically constrained quadratic programming, can be posed by adding quadratic constraints on the variables.
Solution methods
For general problems a variety of methods are commonly used, including
In the case in which Q is positive definite, the problem is a special case of the more general field of convex optimization.
Equality constraints
Quadratic programming is particularly simple when Q is positive definite and there are only equality constraints; specifically, the solution process is linear. By using Lagrange multipliers and seeking the extremum of the Lagrangian, it may be readily shown that the solution to the equality constrained problem
is given by the linear system
where
The easiest means of approaching this system is direct solution (for example, LU factorization), which for small problems is very practical. For large problems, the system poses some unusual difficulties, most notably that problem is never positive definite (even if
If the constraints don't couple the variables too tightly, a relatively simple attack is to change the variables so that constraints are unconditionally satisfied. For example, suppose
introduce a new variable
where
and if
the solution of which is given by:
Under certain conditions on
Lagrangian duality
The Lagrangian dual of a QP is also a QP. To see that let us focus on the case where
Defining the (Lagrangian) dual function
Hence the dual function is
and so the Lagrangian dual of the QP is
Besides the Lagrangian duality theory, there are other duality pairings (e.g. Wolfe, etc.).
Complexity
For positive definite Q, the ellipsoid method solves the problem in polynomial time. If, on the other hand, Q is indefinite, then the problem is NP-hard. In fact, even if Q has only one negative eigenvalue, the problem is NP-hard.