## 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, x_{1}, the minimum wage in Florida, x_{2}, the weather, x_{3}, the cost of transporting the orange juice around the country, x_{4}, . . . and various other factors. . . all the way to x_{N}. The relationship could be stated as

F = **H**(x_{1}, x_{2}, x_{3}, x_{4}, . . . x_{N})

where **H** is the function that defines F in terms of the x_{i}.

Quadratic Programming deals with functions in which the x_{i} are raised to the power of 0, 1, or 2. The goal of Quadratic Programming is to determine the x_{i} 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) **x ^{T} H x + c^{T} 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) x_{1}^{2} - 2 x_{1} x_{2} - x_{1} x_{3} + 2 x_{2}^{2} + 3 x_{2}x_{3} + (5/2) x_{3}^{2} + 2 x_{1} - 35 x_{2} - 47 x_{3} + 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

x_{1} = 3,

x_{2} = 5, and

x_{3} = 7