Quadratic Programming Example #1: No Constraints |
Some Background
Sometimes systems arise in which an output depends upon several variables. For example, the price of orange juice, F, might depend upon the price of real estate in Florida, x1, the minimum wage in Florida, x2, the weather, x3, the cost of transporting the orange juice around the country, x4, . . . and various other factors. . . all the way to xN. The relationship could be stated as
F = H(x1, x2, x3, x4, . . . xN)
where H is the function that defines F in terms of the xi.
Quadratic Programming deals with functions in which the xi are raised to the power of 0, 1, or 2. The goal of Quadratic Programming is to determine the xi for which the function F is a minimum. The system is usually stated in Matrix and vector form.
The general problem of Quadratic Program is stated as follows:
minimize F = (1/2) xT H x + cT x + α
which is usually further defined by a number of constraints (The 1/2 factor is included in the quadratic term to avoid the appearance of a factor of 2 in the derivatives). F is called the objective function, H is a symmetric matrix called the Hessian matrix, c is a vector of constants, and α is a scalar constant.
As an example, say
F = (5/2) x12 - 2 x1 x2 - x1 x3 + 2 x22 + 3 x2x3 + (5/2) x32 + 2 x1 - 35 x2 - 47 x3 + 5
In this case,
H =
5 -2 -1
-2 4 3
-1 3 5
c T = (2 -35 -47)
and α = 5
The example posted on this page assumes no constraints, which is the easiest Quadratic Programming problem to solve. The problem reduces to setting the gradient of the objective function equal to zero and solving the system for this condition.
For the problem at hand (quadratic programming), the gradient, G, is
G = H x + c
Setting the gradient equal to zero:
H x + c = 0
which is rearranged into the following form:
H x = -c
The problem comes down to solving N Equations in N Unknowns.
(Quadratic programming with constraints is a whole other matter!)
A Numerical Example
Consider the example given above.
H =
5 -2 -1
-2 4 3
-1 3 5
c T = (2 -35 -47)
All of the eigenvalues of the H Matrix are greater than 0; in other words, the H Matrix is positive definite--a global minimum should exist. If the H Matrix was not positive definite, a global minimum might not exist; local minima only might be found.
The system to be solved is then
[A](x) = (b)
where A is H and b is -c.
The solution is
x T = (3 5 7)
In other words, F takes a minimum value when
x1 = 3,
x2 = 5, and
x3 = 7