> restart;

>

Lagrange Multipliers

The method of Lagrange multipliers is a useful tool that is helpful in finding minimal, or maximal, that is, optimal values of a given objective function subject to a constraint or , where , are given functions, a given constant. The method can also be used to find optimal values of functions of three or more variables and under more than one constraint.

Let's focus our attention on the problem of the form

Optimize

Subject to: .

Let's label the above optimization problem Problem (OP).

>

The method of Lagrange multipliers is based on a simple observation concerning the perpendicularity of the gradient of the objective function to the constraint curve at an optimal point. Suppose for a moment that Problem (OP) calls for maximizing the objective function. Then, we observe the following: if a point ( ) is a solution to (OP), then the gradient gradf( ) must be perpendicular at ( ) to the curve . Indeed, if it wasn't, we could move a little along the constraint curve advancing in the direction of gradf( ) and thus making the values of the function larger without violating the constraint. Thus, ( ) would not be the point providing the maximal value of . A similar argument holds if we want to minimize the objective function. A similar argument holds if ( ) is only a local minimum or maximum of subject to the constraint . If the gradient gradf( ) is perpendicular to the constraint curve, then it is parallel to the gradient gradg( ), as the latter vector is also perpendicular to the curve . Hence, for some constant , the following system of equations is satisfied at any solution ( ) of (OP): .

gradf( )= gradg( ), g( ) = .

The same system of equations, perhaps with different , is satisfied at any local minimum or maximum of subject to . By finding all solutions ( ) of the system and comparing the corresponding values of we can often find the solution to (OP). The above system of equations can be rewritten in the form

, , ,

where is the so-called Lagrangian of Problem (OP). All three equations above must hold at any optimal point ( ).

Perpendicularity of gradf( ) to the curve implies, of course, the tangency of the constraint curve to the level curve of through ( ) at any solution point ( ).

>

To illustrate the method of Lagrange multipliers, consider the following example.

Example 1. Minimize the function subject to the constraint . (In our example, , .)

When applying the method of Lagrange multipliers, the first question that you should ask yourself is whether the maximum or minimum that you are seeking exists. The Lagrange multipliers method provides a necessary condition for an optimum. It says: if ( ) is a solution, then...and so on. If the maximum or minimum in your problem does not exist, Lagrange multipliers may lead to very erroneous conclusions.

To convince ourselves that the minimum in our example exists, let's plot the function , the constraint curve , and the points on the graph corresponding to the constraint curve, that is, the points on the graph of z=f(x,y) lying above the circle which is the constraint curve here. We shall use a parametric representation of the unit circle . Namely

, , , .

Observe that the points on the graph of that correspond to the points on the unit circle are of the form

( , , .

We shall use the spacecurve command contained in the plots package to plot the unit circle on the xy-plane and the corresponding points on the graph of .

>

> with(plots):

> f:=(x,y)->4-(0.5*x^2+y^2-0.3*x);

> f1:=plot3d(f(x,y),x=-1.5..1.5,y=-1.5..1.5):

> f2:=spacecurve([cos(t),sin(t),f(cos(t),sin(t))],t=0..2*Pi,color=red,thickness=2):

> f3:=spacecurve([cos(t),sin(t),0],t=0..2*Pi,color=red,thickness=2):

> display([f1,f2,f3],axes=framed,scaling=constrained,orientation=[140,80]);

>

Rotate the above graph to convince yourself that the minimum value of along the curve on the graph corresponding to the circle is attained. Actually, it seems that there are two local maxima and two local minima along the curve. To find those local minima and maxima, we shall form the Lagrangian for our problem and have Maple solve the resulting system of equations. We expect the system to have four solutions, corresponding to the four local extrema. Since the notation is awkward, we shall denote the Lagrange multiplier by the letter "a". For simplicity, we define the Lagrangian to be an expresssion in terms of the variables x, y, a, rather than a function.

> L:=f(x,y)-a*(x^2+y^2-1);

>

Let's label the corresponding equations eq1, eq2, etc..

> eq1:=diff(L,x)=0; eq2:=diff(L,y)=0;eq3:=diff(L,a)=0;

>

We use the command solve to solve the system. We denote the resulting solutions by soln .

> soln:=[solve({eq1,eq2,eq3},{x,y,a})];

>

The above system of equations is very simple and Maple has found all the right solutions. You have to be aware, however, that the solve command doesn't always works perfectly, for the simple reason that there are no good algorithms for solving systems of equations. Sometimes the solve command will miss solutions, sometimes it will give you extraneous solutions that are not solutions of your original system. You should always check if the solutions Maple gave you are, indeed, solutions, and try to make sure that you have obtained all possible solutions. We check each solution triple ( ) by substituting it into the original system. Observe that soln is a list. Thus, its i-th element is soln[i] . Since we have four elements in the list, we use the seq command to reduce the amount of typing. Here is our check:

> seq(subs(soln[i],eq1),i=1..4);

> seq(subs(soln[i],eq2),i=1..4);

> seq(subs(soln[i],eq3),i=1..4);

>

All four triples are solutions to our system. We clearly can see two points along the red curve on the graph of at which the function reaches a local maximum, and two points at which the function reaches a local minimum. All four points are, of course, solutions to the Lagrangian system of equations. To check which ones of our four triples give minima and which maxima of , we substitute them into .

> seq(subs(soln[i],f(x,y)),i=1..4);

>

We see that the last two triples in soln correspond to the minimum value of along the circle That is, the minimum value of 2.955 is attained at the points , (approximately), and . The first two triples in soln correspond to local maxima.

Another way to check your answer is by reducing the optimization problem to a problem involving one variable. We want to find the points along the circle , , with between 0 and , at which attains its minimum. Consider the function

> m:=t->f(cos(t),sin(t));

> plot(m(t),t=0..2*Pi);

>

We see clearly two points at which the minimum value of 2.955 is attained, as well as two points at which there is a local maximum. (Remember that and correspond to the same point on the circle .) The points of the minimum value 2.955 correspond to two values of t between 1 and 2 and between 4 and 5.

> fsolve(diff(m(t),t)=0,t,1..2);

> fsolve(diff(m(t),t)=0,t,4..5);

>

The corresponding x and y coordinates on the circle are

> cos(1.875488981);sin(1.875488981);cos(4.407696326);sin(4.407696326);

>

Everything checks out.

Now, we shall plot a contour map of and the constraint circle to illustrate the tangency of contours to the constraint curve at the points of local minima or maxima. We have to make sure that the contours , f(x,y) = 3.2, corresponding to the locally minimal and maximal values of on the circle are included in our contour map. We also shall display the points of local extrema on our graph using the pointplot command. Note a creative use of the subs command in defining for Maple the points p1 , p2 , p3 , p4 of local extrema. We substitute x and y of each triple, soln[i], into a pair [x,y] obtaining a point in the xy-plane.

> C:=contourplot(f(x,y),x=-1.5..1.5,y=-1.5..1.5,contours=[1,1.5,2,2.5,2.955,3.2,3.4,3.6,3.8,4],color=blue):

> K:=implicitplot(x^2+y^2=1,x=-1.5..1.5,y=-1.5..1.5,color=red,thickness=2):

> p1:=subs(soln[1],[x,y]);

> p2:=subs(soln[2],[x,y]);

> p3:=subs(soln[3],[x,y]);

> p4:=subs(soln[4],[x,y]);

> extrema:=pointplot([p1,p2,p3,p4],color=black,symbol=box):

>

> display([C,K,extrema],scaling=constrained,axes=boxed);

>

We can clearly see that contours of and the constraint curve , where , are tangent at the points of local extrema. Hence, gradf(x,y) and gradg(x,y) at those points are parallel.

>

Example 2. Consider the parabolas and on the xy-plane. Find the two points, one on each parabola, whose distance apart is the smallest possible.

The problem can be solved using the Lagrange multipliers method. Let's begin by graphing the parabolas and making sure that there are two such points on the parabolas whose distance is minimal.

> plot([x^2,-(x-1)^2],x=-2..3,color=[red,blue]);

>

Definitely there are two points that are closest. They can be easily found using Lagrange multipliers. There are many ways to set up the problem.

Our objective is to minimize the distance between a point (x,y) on the parabola and a point (X,Y) on the parabola . These are two different points, so we cannot denote the coordinates of both by (x,y). Let's use the notation (x,y) for a point on the first parabola, and (X,Y) for a point on the second parabola. Our objective function is then a function of four variables x, y, X, Y. Instead of minimizing the distance between (x,y) and (X,Y) we can minimize the square of the distance. Indeed, the distance is minimal exactly when its square is minimal. Hence, our objective function is

> S:=(x,y,X,Y)->(x-X)^2+(y-Y)^2;

>

We have two constraints: (x,y) must be on the first parabola, (X,Y) on the second. Hence we have two constraint functions

> F:=(x,y)->y-x^2;

> G:=(X,Y)->Y+(X-1)^2;

>

Our constraints are and . Hence, we have an optimization problem in which the objective function is a function of four variables and we have two constraints. The Lagrangian of the problem contains two multipliers. Let's denote them a and b. The Lagrangian then is of the form

> La:=S(x,y,X,Y)-a*F(x,y)-b*G(X,Y);

>

Now we set up the corresponding system of Lagrangian equations.

> equ1:=diff(La,x)=0; equ2:=diff(La,y)=0; equ3:=diff(La,X)=0; equ4:=diff(La,Y)=0; equ5:=diff(La,a)=0; equ6:=diff(La,b)=0;

>

Now we solve the system. We expect one solution as in the picture of the two parabolas above we don't see more than one local maximum or minimum of the distance between two points on the parabolas.

> sol:=solve({equ1,equ2,equ3,equ4,equ5,equ6},{x,y,X,Y,a,b});

>

We obtained a nasty-looking expression. There are several ways of proceeding. Since we know that we must have only one real solution, we can try fsolve instead of solve . fsolve works much more reliably, but it ususally provides one solution only.

> sol1:=fsolve({equ1,equ2,equ3,equ4,equ5,equ6},{x,y,X,Y,a,b});

>

Here is our solution: the closest points are, approximately, (x,y)=(.3854,.1485) on parabola F and (X,Y)=(.6145,-.1485) on parabola G. We can plot everything in one coordinate system and check.

> pt1:=subs(sol1,[x,y]); pt2:=subs(sol1,[X,Y]);

> plo1:=pointplot([pt1,pt2],color=magenta,symbol=box):

> plo2:=implicitplot(F(x,y)=0,x=-2..2,y=-2..2,color=red):

> plo3:=implicitplot(G(x,y)=0,x=-2..2,y=-2..2,color=blue):

> display([plo1,plo2,plo3],xtickmarks=[-1,0,1,2],scaling=constrained);

>

It looks like we got it right!

>

Homework Problems

Problem 1. Let be our objective function. (Note that the coefficients are decimals 0 .3 and 0 .4 and not 3 and 4.) Let and the ellipse be our constraint. Find the maximum and the minimum values of subject to following the steps below.

(a) Plot the 3d graph of the function , the ellipse in the xy-plane, and the curve on the graph corresponding to the values of along the ellipse in one coordinate system. Use a parametric representation of the ellipse that you should know from last semester. Choose an appropriate range for x and y so you get a really good picture. Use or do not use the scaling=constrained option, whichever gives you a better graph. By looking at the graph, decide whether the minimum and the maximum values of along the ellipse exist and how many solutions you will expect the Lagrangian system of equations to have. Explain your reasoning.

>

(b) Define the Lagrangian function for the optimization problem and set up the corresponding system of equations.

(c) Find solutions to the system using the solve command. Check that you didn't obtain any extraneous solutions. Is the number of solutions what you expected?

(d) Using results of (c), find the minimum and the maximum values of subject to the constraint .

(e) Double check your answer by substituting the parametric representation of the ellipse into and looking at the graph of the resulting function of one variable? Does everything check out?

(f) Plot the constraint curve, a contour map of , and local extrema in one coordinate system. Do you see the tangency of contours and the ellipse at the extremal points? (Hint: In order to see the tangency, you have to use the scaling=constrained option.)

>

Problem 2.

Consider two curves on the xy-plane: and . Find two points (x,y), (X,Y) on each of the two curves, respectively, whose distance apart is as small as possible. Use the method of Lagrange multipliers. Make a graph that illustrates your solution.

>

MTH 243 Maple Worksheets written by B. Kaskosz and L. Pakula, Copyright 1999.

>