Quadratic Programming

Quadratic programming (QP) is the process of solving a special type of optimization problem, namely the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables. Quadratic programming is a special case of nonlinear programming.

Problem formulation

A quadratic programming problem with n variables and m constraints can be formulated as follows .

Given:

• a real n-dimensional vector c,
• an n × n-dimensional real symmetric matrix Q,
• an m × n-dimensional real matrix A
• a real m-dimensional vector b,

the goal of the quadratic programming problem is to find an n-dimensional vector x that

minimizes
subject to

where x^T denotes the transposed vector. The notation Ax ≤ b means that every element of the vector Ax does not exceed the corresponding element of the vector b.

A related programming problem, the quadratically constrained quadratic program , has quadratic constraints on the variables.

Solution methods

For general values, various methods are used, among them

• Interior point method
• Active set method
• Augmented Lagrangian method
• Conjugate gradient method
• Gradient projection method
• Modification of the simplex method

When Q is positive definite, the problem is a special case of the more general problem of convex optimization.

Equality constraints

The quadratic programming problem is somewhat simpler if Q is positive definite and all the constraints are equalities (there are no inequalities), since in this case the problem can be reduced to solving a system of linear equations. Using Lagrange multipliers and seeking the extremum of the Lagrangian, one can easily show that the solution of the problem

minimize
subject to

is determined by the system of linear equations

where is the set of Lagrange multipliers that appear together with the solution .

The easiest way to solve this system is to solve it by direct methods (for example, using LU decomposition, which is very convenient for small problems). For large problems some unusual difficulties arise, most noticeably when the problem is not positive definite (even if is positive definite), which potentially makes it very difficult to find a good mathematical approach, and there are many problem-dependent approaches .

If the number of constraints is not equal to the number of variables, one can try a relatively simple attack by substituting variables in such a way that the constraints are satisfied unconditionally. For example, suppose that (moving to nonzero values is simple enough). Consider the constraints

Introduce a new vector , defined by the equality

where has dimension minus the number of constraints. Then

and if the matrix is chosen so that , the equality constraints will always be satisfied. Finding the matrix involves finding the kernel of the matrix , which is more or less easy, depending on the structure of the matrix . Substituting the new vector into the original conditions, we obtain an unconstrained quadratic problem:

and the solution can be found by solving the equation

Under certain restrictions on the reduced matrix will be positive definite. One can write a variant of the conjugate gradient method in which there is no need to compute the matrix explicitly .

Lagrangian duality. The dual problem

The Lagrangian dual problem for quadratic programming is also a quadratic programming problem. To see this, let us consider the case with a positive definite matrix Q. Let us write out the Lagrange multipliers of the function

If we define the (Lagrangian) dual function as , we seek a lower bound , using and the positive definiteness of the matrix Q:

Consequently, the dual function is equal to

and the Lagrangian dual problem for the original problem will be

minimize
subject to	.

Besides Lagrangian duality theory, there are other dual pairs of problems (for example, Wolfe duality ).

Complexity

For a positive definite matrix Q, the ellipsoid method solves the problem in polynomial time . If, on the other hand, Q is not positive definite, then the problem becomes NP-hard . In fact, even if Q has a single negative eigenvalue, the problem is NP-hard .

Quadratic programming finds the values of the variables x that minimize or maximize a quadratic objective function while satisfying all the constraints. A solution of a quadratic optimization problem can be obtained using various methods, including the active set method, the interior point method, the sequential quadratic programming method, and others.

Applications

Quadratic programming is widely used in many fields, including finance, engineering design, economics, statistics, production management, and others, where it is necessary to solve an optimization problem with quadratic functions and linear or quadratic constraints.

See also

• Support vector machine
• Sequential quadratic programming
• Linear programming