Here's a little maths trick called the Lagrange Multiplier that helps in finding the maximum/minimum of a function f(x, y) given a constant that also uses x and y. We "form the function

F(x, y) = f(x, y) + λ Φ(x, y)

and set the two partial derivatives of F equal to zero. Then solve these two equations and the equation Φ(x, y) = constant for the three unknowns x, y and λ".

A nice proof can be found in the essential undergraduate text, Mathematical Method in the Physical Sciences. Let's say we're trying to find the max/min of the function f(x, y). Obviously, at this point.

df =

__δf__dx +

__δf__dy = 0 (1)

δx δy

and say we've been given a function that is a constant Φ(x, y). Once again, it should be obvious that:

dΦ =

__δ__

__Φ__dx +

__δ__

__Φ__dy = 0 (2)

δx δy

since Φ(x, y) is a constant.

Now, multiply the second equation by λ and add it to the first.

(

__δf__+ λ

__δ__

__Φ__)dx + (

__δf__+ λ

__δ__

__Φ__)dy = 0 (3)

δx δx δy δy

Let's take that second term. Since λ is arbitrary, let's choose it to be such that:

__δf__+ λ

__δ__

__Φ__= 0 (4)

δy δy

(That is, we've decided

λ = -

__δf__/

__δ__

__Φ__(5)

δy / δy

But it's not necessary to worry about that as we're not particularly interested in the value of λ. We just use it to solve the equations).

Similarly, we do the same for the first term of (3):

__δf__+ λ

__δ__

__Φ__= 0 (6)

δx δx

Now, with equations (4) and (5) and (6) we have enough information to find the values of x and y at the position of the min/max point.

__Example__

The best way to understand this, I found, was an example from Boaz. Say, we're given:

f(x) = x

^{2}+ y

^{2}

and the constraint:

ϕ(x,y) = x

^{2}+ y = 1

Then, the equation to minimize is:

F(x,y) = f(x,y) + λ ϕ(x,y) = x

^{2}+ y

^{2}+ λ(x

^{2}+ y)

Because ϕ is a constant and will disappear when we differentiate, this point of minimization is exactly that of f(x,y) which is what we really want to find. So:

__δF__= 2y + λ = 0

δy

and

__δF__= 2x + 2λx = 0

δx

that is, either x=0 or λ=-1.

If, x=0, y=1 (from the equation for ϕ) and λ=-2 (from the first differential equation).

If λ=-1, then y=½ (from the first differential equation) and x

^{2}=½ (from the equation for ϕ).

QED.

__Conclusion__

Why am I writing this post? Because we're going to need the Lagrange Multiplier shortly in partitioning a graph.

## No comments:

## Post a Comment