Saturday, September 3, 2016

Yet more maths and graphs - Lagrange Multiplier


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) = x2 + y2

and the constraint:

ϕ(x,y) = x2 + y = 1

Then, the equation to minimize is:

F(x,y) = f(x,y) + λ ϕ(x,y) = x2 + y2 + λ(x2 + 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 x2=½ (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