{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 1 12 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1
257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0
0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1
{CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 6 6 0 0
0 0 0 0 -1 0 }{PSTYLE "Bullet Item" 0 15 1 {CSTYLE "" -1 -1 "" 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 3 3 0 0 0 0 0 0 15 2 }{PSTYLE ""
0 256 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0
-1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 1
14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }
{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0
1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1
-1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1
0 }{PSTYLE "" 3 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {PARA 260 "" 0 "" {TEXT -1 30 "Maximization, with Constraints
" }}{PARA 256 "" 0 "" {TEXT -1 9 "Jim Herod" }}{PARA 257 "" 0 ""
{TEXT -1 21 "School of Mathematics" }}{PARA 258 "" 0 "" {TEXT -1 12 "G
eorgia Tech" }}{PARA 259 "" 0 "" {TEXT -1 21 "herod@math.gatech.edu" }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 308 " We present a classical method for m
aximizing a function with constraints. As a beginning, we illustrate t
he methods. The first problem will be to find the point on an ellipse \+
that is closest to and furthest from the point [4/5 , 4/5]. The follow
ing will draw the picture of the ellipse and the point P. " }}{PARA 0
"" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "with
(plots): with(plottools): with(linalg):" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 108 "J1:=implicitplot(2*x^2+5*y^2=1,x=-4..4,y=-4..4,grid=
[75,75]):\nK1:=textplot([4/5,4/5,`P`]):\ndisplay(\{J1,K1\});" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 173 "The problems are commonly stat
ed this way: maximize (or minimize) f(x, y) subject to the constraint \+
g(x, y) = 0. For the problem above, we would say: Maximize (and minimi
ze)" }}{PARA 0 "" 0 "" {TEXT -1 44 " \+
" }{XPPEDIT 18 0 "(x-4/5)^2+(y-4/5)^2" "6#,&*$,&%\"xG\"\"\"*
&\"\"%F'\"\"&!\"\"F+\"\"#F'*$,&%\"yGF'*&F)F'F*F+F+F,F'" }{TEXT -1 2 " \+
" }}{PARA 0 "" 0 "" {TEXT -1 25 "subject to the constraint" }}{PARA
0 "" 0 "" {TEXT -1 54 " g(
x,y) = " }{XPPEDIT 18 0 "2*x^2+5*y^2-1=0" "6#/,(*&\"\"#\"\"\"*$%\"xGF&
F'F'*&\"\"&F'*$%\"yGF&F'F'F'!\"\"\"\"!" }{TEXT -1 1 "." }}{PARA 0 ""
0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 13 "Naive method
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "Here
is a completely naive method for thinking about the problem. We think
of maximizing " }}{PARA 0 "" 0 "" {TEXT -1 52 " \+
f(x,y) = " }{XPPEDIT 18 0 "(x-4/5)^2+(y-4/5)^2" "
6#,&*$,&%\"xG\"\"\"*&\"\"%F'\"\"&!\"\"F+\"\"#F'*$,&%\"yGF'*&F)F'F*F+F+
F,F'" }}{PARA 0 "" 0 "" {TEXT -1 177 "subject to the constraint that t
he point [x, y] lies on the ellipse specified by g. We parameterize t
he ellipse. One way to parameterize the constraint curve would be to a
ssign" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "
x(t) = " }{XPPEDIT 18 0 "cos(t)/sqrt(2)" "6#
*&-%$cosG6#%\"tG\"\"\"-%%sqrtG6#\"\"#!\"\"" }{TEXT -1 20 " and \+
y(t) = " }{XPPEDIT 18 0 "sin(t)/sqrt(5)" "6#*&-%$sinG6#%\"tG\"\"\"-%%
sqrtG6#\"\"&!\"\"" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 41 "Then g( x(t), y(t) ) = \+
" }{XPPEDIT 18 0 "cos(t)^2+sin(t)^2-1" "6#,(*$-%$cosG6#%\"tG\"\"#\"\"
\"*$-%$sinG6#F(F)F*F*!\"\"" }{TEXT -1 6 " = 0. " }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "Thus, for each t, [x(t),
y(t)] is on the constraint curve. We wish to choose t to maximize (an
d minimize)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT
-1 48 " h(t) = f(x(t), y(t)). " }}{PARA 0 ""
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "We do this." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "The funct
ion we want to maximize is" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
30 "f:=(x,y)->(x-4/5)^2+(y-4/5)^2;" }}}{PARA 0 "" 0 "" {TEXT -1 54 "Th
e constraint is that the following function is zero." }}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 24 "g:=(x,y)->2*x^2+5*y^2-1;" }}}{PARA 0 ""
0 "" {TEXT -1 39 "The parameterization [xp(t), yp(t)] is" }}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "xp:=t->cos(t)/sqrt(2);\nyp:=t->sin(
t)/sqrt(5);" }}}{PARA 0 "" 0 "" {TEXT -1 120 "We check to see that the
suggested parameterization for g(x,y) = 0 really is a parameterizatio
n. That is, we check that " }}{PARA 0 "" 0 "" {TEXT -1 48 " \+
g(x(t), y(t) ) = 0." }}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 25 "simplify(g(xp(t),yp(t)));" }}}{PARA 0 "" 0 "" {TEXT
-1 87 "Now, we make the function h that depends only on t and is defin
ed as h( xp(t), yp(t) )." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "
h:=t->f(xp(t),yp(t));" }}}{PARA 0 "" 0 "" {TEXT -1 193 "From the graph
of the ellipse above, we guess there are two places where the derivat
ive is zero -- one gives a maximum and the other gives a minimum. This
can be seen by drawing the graph of h." }}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 21 "plot(h(t),t=0..2*Pi);" }}}{PARA 0 "" 0 "" {TEXT -1
96 "Look at the graph of h and guess an interval that contains the two
roots of the derivative of h." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 77 "r1:=fsolve(diff(h(t),t)=0,t,t=0..1);\nr2:=fsolve(diff(h(t),t)=0,
t,t=3.5..4.5);" }}}{PARA 0 "" 0 "" {TEXT -1 43 "We now find the maximu
m and minimum value. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "eva
lf(h(r1)); evalf(h(r2));" }}}{PARA 0 "" 0 "" {TEXT -1 65 "Here are the
coordinates for where the maximum and minimum occur." }}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 45 "sol1:=[xp(r1),yp(r1)]; sol2:=[xp(r2),yp(r
2)];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "evalf(sol1); evalf(
sol2);" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 ""
{TEXT -1 29 "Criticism of the naive method" }}{PARA 0 "" 0 "" {TEXT
256 143 "\nThe method had a good perspective: It changes the problem t
o one dimensional, differential calculus and uses ideas that we alread
y understand." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT -1 247 "The down-side to the method is that we can not be sure t
hat we can find a parameterization for g(x ,y) = 0 in more general sit
uations. For this problem, the constraint was simple enough that we we
re able to find a parameterization for g(x,y) = 0. " }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 127 "We re-do the problem i
n a situation that generalizes, not only for more complicated constrai
nts, but even to higher dimensions." }}}{PARA 0 "" 0 "" {TEXT -1 0 ""
}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 14 "Draw a picture" }}{PARA 0 "" 0
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172 "There is a picture as
sociated with the method we will describe. We draw a picture of the co
nstraint g(x,y) = 0 and of the contours for the function f(x,y) to be
maximized." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 127 "J2:=implicit
plot(g(x,y)=0,x=-4..4,y=-4..4,grid=[75,75]):\nK2:=contourplot(f(x,y),x
=-1..1,y=-1..1,contours=12):\ndisplay(\{J2,K2\});" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 225 "Here is th
e important part: If a contour curve for f(x,y) crosses the constraint
curve g(x,y) = 0, then at the crossing point, the constraint curve is
moving from a point of lower value for f(x,y) to a point of higher va
lue. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172
"The implication of this observation is that we will want a point on t
he constraint curve g(x,y) = 0 where the contour curve for f(x,y) is t
angent to the graph of g(x,y)=0. " }}{PARA 0 "" 0 "" {TEXT -1 100 " \+
We draw the picture and show points that cannot be a maximum or mini
mum of f on the constraint." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA
0 "" 0 "" {TEXT 257 18 "A. Not acceptable!" }{TEXT -1 84 " the values \+
of f increase on one side or the other across this contour curve for \+
f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 14 "B.
This is it!" }{TEXT -1 103 " At this place the values of f on the con
straint g lie on the same side of the f(x,y) = constant curve." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
77 "L2:=textplot(\{[-.3,.45,`A`],[-.7,-.2,`B`],[.6,.3,`B`]\}):\ndispla
y(\{J2,K2,L2\});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{PARA 0 "" 0 "" {TEXT -1 179 "This picture should suggest the followin
g situation: The maximum or minimum occurs where contour curves for f \+
are tangent to the graph of g(x,y) = 0. These points are marked with \+
" }{TEXT 260 1 "B" }{TEXT -1 7 " above." }}}{PARA 0 "" 0 "" {TEXT -1
0 "" }}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 18 "Method of Lagrange" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 113 "The pict
ure from the last section suggested a general method which we describe
here. The problem is the following" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 15 "" 0 "" {TEXT -1 78 "Suppose that each of f and g have conti
nuous partial derivatives and map from " }{XPPEDIT 18 0 "R^2" "6#*$%\"
RG\"\"#" }{TEXT -1 125 " to R. We wish to find the maximum (or minimum
) of a function f at a point [x,y], subject to the constraint that g(
x,y) = 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
289 "The above example suggest that we should ask that the equi-contou
rs of f(x,y) should be tangent to the constraint curve g(x.y) = 0. To \+
find such points, the standard method is to find where the normal to t
he contour has the same direction as the normal to the constraint curv
e. Look again." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 348 "J3:=impli
citplot(2*x^2+5*y^2=1,x=-4..4,y=-4..4,grid=[75,75],scaling=constrained
):\nK3:=implicitplot((x-4/5)^2+(y-4/5)^2=h(r1),x=-4..4,y=-4..4,grid=[7
5,75],\n color=BLUE,scaling=constrained):\nL3:=implicitplot((x-4
/5)^2+(y-4/5)^2=h(r2),x=-4..4,y=-4..4,grid=[75,75],\n color=BLUE
,scaling=constrianed):\ndisplay(\{J3,K3,L3\},scaling=constrained);" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT
-1 148 "To find the point of common tangency, we find where the normal
to the constraint curve is parallel to the normal for the contour. We
draw a picture." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "with(plo
ts): with(plottools):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "H3
:=arrow([xp(r1),yp(r1)], [.6,.6], .01, .1, .1, color=green):" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "display(\{J3,K3,H3\},scaling
=constrained);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "Thus, we \+
seek [x, y] where the gradient of f is a multiple of the gradient of g
: " }}{PARA 0 "" 0 "" {TEXT -1 39 " grad(f
) = " }{XPPEDIT 18 0 "lambda" "6#%'lambdaG" }{TEXT -1 10 " grad (g)."
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 53 "Gradf:=grad(f(x,y),[x,y]);\nGradg:=grad(g(x,y),[x,y]);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "eq:=evalm(Gradf-lambda*Gradg
);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "solve(\{eq[1]=0,eq[2]
=0,2*x^2+5*y^2-1=0\},\{x,y,lambda\});" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 20 "evalf(allvalues(%));" }}{PARA 0 "> " 0 "" {MPLTEXT 1
0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 50 "Recall that these are the solut
ions we got by the " }{TEXT 259 5 "naive" }{TEXT -1 8 " method." }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "evalf(sol1);\nevalf(sol2);"
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 523 "In this example, the las
t step -- solving three equations in three unknowns -- seemed easy. It
is not always easy to solve three nonlinear equations in three unknow
ns. In complicated cases, one might think of a multidimensional Newton
's method. Further, after the equations are solved, which solution giv
es a maximum and which gives a minimum (and which solutions are neithe
r) remains to be decided. Making this determination could be made with
a little computing of particular values, or perhaps from looking at a
picture." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 ""
{TEXT -1 18 "Worked out example" }}{PARA 0 "" 0 "" {TEXT -1 13 "The ge
ometry:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "restart: \nwith(p
lots): with(plottools): with(linalg):" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 14 "f:=(x,y)->x*y;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT
1 0 18 "g:=(x,y)->2*x+y-2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
102 "J2:=implicitplot(g(x,y)=0,x=-2..2,y=-2..2):\nK2:=contourplot(f(x,
y),x=-2..2,y=-2..2):\ndisplay(\{J2,K2\});" }}}{PARA 0 "" 0 "" {TEXT
-1 13 "The calculus:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Grad
f:=grad(f(x,y),[x,y]);\nGradg:=grad(g(x,y),[x,y]);" }}}{EXCHG {PARA 0
"> " 0 "" {MPLTEXT 1 0 30 "eq:=evalm(Gradf-lambda*Gradg);" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "solve(\{eq[1]=0,eq[2]=0,g(x,y)=0\},
\{x,y,lambda\});" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f(1/2,1)
;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1
{PARA 3 "" 0 "" {TEXT -1 23 "Example for the reader." }}{PARA 0 "" 0 "
" {TEXT -1 47 "Find the minimum value taken on by the function" }}
{PARA 0 "" 0 "" {TEXT -1 44 " f(x, y)
= " }{XPPEDIT 18 0 "x^2+(y-2)^2" "6#,&*$%\"xG\"\"#\"\"\"*$,&%\"yGF'F&
!\"\"F&F'" }}{PARA 0 "" 0 "" {TEXT -1 16 "on the hyperbola" }}{PARA 0
"" 0 "" {TEXT -1 34 " " }{XPPEDIT 18
0 "x^2-y^2=1" "6#/,&*$%\"xG\"\"#\"\"\"*$%\"yGF'!\"\"F(" }{TEXT -1 1 ".
" }}}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
}{MARK "0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2
33 1 1 }