\magnification=\magstep1
\centerline{Mathematics 241 -- Multivariable Calculus}
\centerline{Lab Day 4 -- Constrained Optimization and the Geometry of Lagrange Multipliers}
\centerline{November 5, 2007}
\bigskip
\noindent
{\it Background}
\bigskip
In last Friday's class, we started to investigate the problem of
determining where a function $f(x,y)$ took its maximum and minimum
values on curve in the plane $g(x,y) = 0$ (such as the boundary of
a compact region).  The general name for this sort of problem is
{\it constrained optimization}, and the curve $g(x,y) = 0$ is often
called the {\it constraint set} in this context.  Today, we want
to look at some examples of this, and try to see the geometry 
behind a method for solving problems of this form -- the {\it Method
of Lagrange multipliers}.  
\bigskip
\noindent
{\it Lab Work, Part 1}
\bigskip
In the first parts of this lab you will be working through a 
collection of examples designed to help you visualize what
is happening when we look at a maxima and minima of a 
function $f(x,y)$ on a constraint
set $g(x,y) = 0$.  The goal is to try to see a connection between
the constraint set and the {\it level curves} of the function
$f(x,y)$ when $f(x,y)$ reaches a maximum or minimum on the 
constraint set.  
\bigskip
\noindent
{\it Example 1}
\bigskip
Enter the following commands as directed and answer questions A,B,C
in text regions in your Maple worksheet.
Our first example will study the function
$$f(x,y) = x^2 + {y^2\over 2}$$
on the constraint set defined by 
$$g(x,y) = {x^2\over 2} + y^2 - 1 = 0$$ 
(an ellipse).   First we will construct a composite Maple plot of the level curves
of $f$ together with the constraint curve.  To plot the level curves
of $f$ superimposed on the constraint curve, enter the commands
\medskip
\centerline{\tt with(plots):}
\centerline{\tt fPlot1:=contourplot(x\^{}2 + y\^{}2/2, x=-3..3,y=-3..3,contours=31):}
\centerline{\tt gPlot1:=plot([sqrt(2)*cos(t),sin(t),t=0..2*Pi],color=blue):}
\centerline{\tt display(fPlot1,gPlot1,scaling=constrained);}
\medskip
\noindent
What is this doing?
\medskip
\item{$\bullet$}  The {\tt contourplot} command generates a plot of the level curves
and saves the specification of the plot under the name {\tt fPlot}.
It plots the portions of 31 level curves contained in the square in 
the plane with $-3 \le x,y \le 3$.   Maple chooses the $c$-values
for the level curves here, and those are {\it not displayed in the graph}.
 In drawing this graph, Maple
selects $c$-values to use to display as many level curves as possible 
``filling out'' the square.  It is also possible to specify the $c$-values 
we want.  We'll see how to do that later.  
\item{$\bullet$}  The {\tt plot} command draws the constraint curve, using
a standard set of parametric equations for the ellipse, and saves that under
the name {\tt gPlot}.
\item{$\bullet$}  The {\tt display} command superimposes the two plots
on the same set of coordinate axes.
\medskip
\noindent
If you look at the form of the function $f(x,y)$, you will see
that the level curves of $f$ are ellipses also, and the farther the ellipse is
out from the origin, the larger the $c$-value would be in the equation
$f(x,y) = c$ defining the level curve.  
\bigskip
\item{A)}  By examining your plot, try to determine where $f(x,y)$ reaches
its minimum and maximum values on the constraint curve.  Give approximate 
$(x,y)$-coordinates of those points by ``eyeballing'' the composite plot of the level
curves and the constraint curve.
\bigskip
\noindent
Next, we want to look at the function $f(x,y)$ {\it restricted to the constraint
curve} in a different way.  As we saw above in plotting the constraint curve,
it is natural to describe that ellipse by the parametric equations:
$$x = \sqrt{2} \cos(t), \quad y = \sin(t).$$
Let's see what happens if we substitute these into $f(x,y)$ to obtain
$$f\left(\sqrt{2}\cos(t),\sin(t)\right) = \left(\sqrt{2} \cos(t)\right)^2 + {(\sin(t))^2\over 2} = 2\cos^2(t) + {\sin^2(t) \over 2}.$$
Plot this function of $t$ on the interval $0 \le t \le 2\pi$ using the 
following Maple command:
\medskip
\centerline{\tt plot(2*cos(t)\^{}2 + sin(t)\^{}2/2, t = 0..2*Pi);}
\medskip
\noindent
The interval $0 \le t \le 2\pi$ of parameter values takes us
once around the constraint ellipse in the counterclockwise direction, starting
from $(\sqrt{2},0)$ when $t = 0$. 
\medskip
\item{B)}  How does this new plot correspond to what you said in part A?
Give approximate $t$ values corresponding to all local maxima and local
minima of $f$ on the constraint curve and indicate which $(x,y)$ points
from part $A$ correspond to which.

\medskip
\noindent
Now for the most important point.  Look at the graph of $f$ restricted
to the constraint curve.  You should see that the maximum value $f$-value attained
is apparently $2$, and the minimum is apparently $1/2$.  Let's actually go
back and draw {\it just the level curves for those two $c$-values} together 
with the constraint curve and try to understand what is happening.  To 
do this, enter the commands
\medskip
\centerline{\tt newfPlot1:=contourplot(x\^{}2 + y\^{}2/2, x=-3..3,y=-3..3,contours=[0.5,2]):}
\centerline{\tt display(newfPlot1,gPlot1,scaling=constrained);}
\medskip
\noindent
This will display the level curves for just the two given $c$-values, $c = 0.5$ and $c = 2$,
superimposed on the plot of the constraint curve.  Note, the command defining
{\tt gPlot1} from before saved the result under that name so we can reuse it here
without having to generate that plot again.  
\medskip
\item{C)}  What is true about these two contours and the constraint curve where
they meet?  How would you describe the way they meet?
\bigskip
\noindent
{\it Example 2}
\bigskip
Modify the commands given above to generate plots for the function
$$f(x,y) = x^2 - 2 y^2$$
on the constraint set
$$g(x,y) = (x - 1)^2 + (y - 1)^2 - 1 = 0.$$
First generate a plot showing 31 level curves of $f$ superimposed on the 
constraint set.  Note that the constraint set is a circle of radius 1
centered at the point $(1,1)$.  The most convenient parametric equations 
to use for the constraint curve will be 
$$x = 1 + \cos(t) \qquad y = 1 + \sin(t).$$
Now the interval $0 \le t \le 2\pi$ takes you once around the circle
in the counterclockwise direction starting from the point $(2,1)$.  
Then, generate a plot of $f(1 + \cos(t),1 + \sin(t))$ and identify
the $t$-values where the local maxima and minima occur and the corresponding
$(x,y)$.  Finally, determine the $c$-values for the level curves of $f$
at the maximum and minimum points, and plot those level curves together
with the constraint set.    
Answer questions A,B,C in Example 1 above for this example in text regions
in this section of your Maple worksheet.
\bigskip
\noindent
{\it Example 3}
\bigskip
Here is a somewhat more elaborate example.  Consider the function 
$$f(x,y) = y^2 - x^3 + x^2$$
on the constraint curve with equation:
$$g(x,y) = 250x^2 - 930 xy + 1521 y^2 - 729 = 0.$$
As you might recognize, the constraint curve is 
a rotated ellipse.  It can be given in parametric form as:
$$x = \cos(t) + {12 \over 5}\sin(t) \qquad y = -{1\over 3}\cos(t) + \sin(t).$$
Here we want to start in directly by studying the restriction of the 
function $f(x,y)$ to the constraint curve.  Let's plot that to begin with.
Enter the following commands to define the function $f(x,y)$, then 
substitute $x = \cos(t) + {12\over 5}\sin(t)$ and $y = -{1\over 3}\cos(t) + \sin(t)$
into $f(x,y)$, then plot the substituted function:
\medskip
\centerline{\tt f := y\^{}2 - x\^{}3 + x;}
\centerline{\tt foncon := subs($\{$x = cos(t) + 12*sin(t)/5,y=-cos(t)/3 + sin(t)$\}$,f);}
\centerline{\tt plot(foncon,t=0..2*Pi);}
\medskip
\noindent
You should see a very ``interesting'' graph with {\it six} critical points -- 
three local maxima and three local minima.
\medskip
\item{A)}  Estimate the $t$-values where these occur and the values of $f$
at the critical points from the graph.
\medskip
Now we want to understand how the level curves of $f$ are meeting the constraint
curve at the locations of these local maxima and minima.  
\medskip
\item{B)}  As in part C of Examples 1 and 2 above, plot the level curves
of $f(x,y)$ for the $c$-values coming from the values of $f(x,y)$ at the local
maxima and minima from part A here.  Combine with a parametric plot of the 
constraint curve to produce a picture like the ones from part C of Examples
1 and 2.  What is true about the way the level curve of $f(x,y)$ meets
the constraint curve in each case?
\bigskip
\noindent
{\it Lab Work, part 2 -- Lagrange multipliers}
\bigskip
The geometry we are seeing in Examples 1, 2, and 3 is the basis for the 
{\it method of Lagrange multipliers} for solving constrained optimization
problems.  As we will see in class on Tuesday November 6, the idea is
that the geometry of the way the level curves of the objective function
$f(x,y)$ met the constraint curve at the maximum or minimum points in 
those examples is a general phenomenon.  It 
can also be generalized to any number of variables.  This
leads to the the following condition.  In the plane, if $f(x,y)$ has a local maximum 
or minimum on the constraint curve at $(x,y) = (a,b)$, then 
$$\nabla f(a,b) = \lambda \nabla g(a,b)$$
for some scalar $\lambda$ called the {\it Lagrange multiplier}.  (The
same equation holds at any critical point of the restriction of 
$f(x,y)$ to the constraint curve.)  Similarly, if $f(x,y,z)$ has a 
local maximum or minimum on the constraint surface $g(x,y,z) = 0$
at $(x,y,z) = (a,b,c)$, then 
$$\nabla f(a,b,c) = \lambda \nabla g(a,b,c).$$
To 
find these points we can set up the system of equations
$$\eqalign{f_x(x,y,z) &= \lambda g_x(x,y,z)\cr
           f_y(x,y,z) &= \lambda g_y(x,y,z)\cr
           f_z(x,y,z) &= \lambda g_z(x,y,z)\cr
           g(x,y,z) & = 0\cr}\leqno(1)$$
and try to solve for $(x,y,z,\lambda)$.  For relatively simple
problems like some of the questions on this week's problem set 
from section 4.3, this can be done ``by hand.''  More complicated
examples are often solved using computers and numerical methods
for solving systems of equations like the features of Maple
we will see next.  

\bigskip
\noindent
{\it Worked Example 4}
\bigskip
The problem is to find the critical points of $f(x,y,z) = 3xy - 4z^2 + x$
on the constraint surface defined by $3x + y - 2xz - 1 = 0$.  
First we define the functions $f$ and $g$ using:
\medskip
\centerline{\tt f := 3*x*y-4*z\^{}2+x;}
\centerline{\tt g := 3*x+y-2*x*z-1;}
\medskip
\noindent 
Then the Lagrange multiplier equations (1) can be set up 
using a command like this:
\medskip
\centerline{\tt LMEqs := $\{$diff(f,x)-lambda*(diff(g,x)), diff(f,y)-lambda*(diff(g,y)),}
\centerline{\tt $\qquad\qquad$ diff(f,z)-lambda*(diff(g, z)), g$\}$;}
\medskip
\noindent
The {\tt diff} command is Maple's symbolic differentiation command.  You can 
use it for partial derivatives as here by specifying which variable you 
are differentiating with respect to.
Then enter the following command to look for a solution of the system 
of Lagrange multiplier equations using Maple's numerical routine called {\tt fsolve}:
\medskip
\noindent
\centerline{\tt S1 := fsolve(LMEqs, $\{$x, y, z, lambda$\}$);}
\medskip
\noindent
When I ran this command in Maple on my office computer, the results were (edited to show
only 5 decimal places):
\medskip
\centerline{\tt S1 := $\{$y = 0.33333, lambda = -4.54326, x = -1.51442, z = 1.72010$\}$}
\medskip
\noindent
This should be self-explanatory.  

The natural question to ask at this point is: {\it Is this vector 
$(x,y,z,\lambda)$ the only solution of the 
Lagrange multiplier equations?}  The answer is {\it no}!  If you 
decide you want to look for other solutions, one way is to enter 
starting values for $x,y,z,\lambda$ like this:
\medskip
\noindent
\centerline{\tt S2 := fsolve(LMEqs, $\{$x=0, y=0, z=0, lambda=0$\}$);}
\medskip
\noindent
This should give a second, distinct solution vector.
You can think of this as saying -- ``OK, Maple, look for a solution of the 
system of equations {\it starting from} $(x,y,z,\lambda) = (0,0,0,0)$.''
The solution you get will often be close to the starting point you specify if
there is one.  On occasion, you will just get the input command back.  This
means that Maple's routine failed to find a solution in a reasonable amount
of time, so it stopped looking.  

There is one additional solution too.  See if you can find it.
\bigskip
\noindent
{\it Example 5}
\bigskip
Use the techniques illustrated above to find as many distinct solutions
of the Lagrange Multiplier equations for the constrained optimization
problem from Problem 13 in Section 4.1 of the text as you can.  (Full credit
for four distinct ones, but there are quite a few more than that, and you will 
earn Extra Credit for each additional one you find using Maple (!)) 

\bye  
