TRENCH_LAGRANGE_METHOD

THE METHOD OF LAGRANGE MULTIPLIERS William F. Trench Andrew G. Cowles Distinguished Professor Emeritus Department of Mathematics Trinity University San Antonio, Texas, USA [email protected] This is a supplement to the author’s Introduction to Real Analysis . It has been judged to meet the evaluation criteria set by the Editorial B oard of the American Institute of Mathematics in connection with the Institute’ sOpen Textbook Initiative . It may be copied, modified, redistributed, translated, and b uilt upon subject to the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported Lice nse. A complete instructor’s solution manual is available by emai l [email protected] , subject to verification of the requestor’s faculty status. THE METHOD OF LAGRANGE MULTIPLIERS William F . Trench 1 Foreword This is a revised and extended version of Section 6.5 of my Advanced Calculus (Harper & Row, 1978). It is a supplement to my textbook Introduction to Real Analysis , which is referenced via hypertext links. 2 Introduction To avoid repetition, it is to be understood throughout that fandg1,g2,. . . ,gmare continuously differentiable on an open set DinRn. Suppose that m < n and g1.X/Dg2.X/D /SOH /SOH /SOH D gm.X/D0 (1) on a nonempty subset D1ofD. IfX02D1and there is a neighborhood NofX0such that f .X//DC4f .X0/ (2) for every XinN\D1, then X0isa local maximum point of fsubject to the constraints (1). However, we will usually say “subject to” rather than “sub ject to the constraint(s).” If (2) is replaced by f .X//NAKf .X0/; (3) then “maximum” is replaced by “minimum.” A local maximum or m inimum of f subject to ( 1) is also called a local extreme point of fsubject to (1). More briefly, we also speak of constrained local maximum, minimum, or extreme points . If ( 2) or ( 3) holds for all XinD1, we omit “local.” Recall that X0D.x10; x20; : : : ; x n0/is acritical point of a differentiable function LDL.x 1; x2; : : : ; x n/if Lxi.x10; x20; : : : ; x n0/D0; 1 /DC4i/DC4n: Therefore, every local extreme point of Lis a critical point of L; however, a critical point of Lis not necessarily a local extreme point of L(pp. 334-5) . Suppose that the system ( 1) of simultaneous equations can be solved for x1, . . . , xmin terms of the xmC1, . . . , xn; thus, xjDhj.xmC1; : : : ; x n/; 1 /DC4j/DC4m: (4) Then a constrained extreme value of fis an unconstrained extreme value of f .h 1.xmC1; : : : ; x n/; : : : ; h m.xmC1; : : : ; x n/; xmC1; : : : ; x n/: (5) 2 However, it may be difficult or impossible to find explicit for mulas for h1,h2, . . . , hm, and, even if it is possible, the composite function ( 5) is almost always complicated. Fortunately, there is a better way to to find constrained extr ema, which also requires the solvability assumption, but does not require an explici t formula as indicated in ( 4). It is based on the following theorem. Since the proof is compl icated, we consider two special cases first. Theorem 1 Suppose that n > m: IfX0is a local extreme point of fsubject to g1.X/Dg2.X/D /SOH /SOH /SOH D gm.X/D0 and ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@g1.X0/ @[email protected]/ @xr2/SOH /SOH /[email protected]/ @xrm @g2.X0/ @[email protected]/ @xr2/SOH /SOH /[email protected]/ @xrm:::::::::::: @gm.X0/ @[email protected]/ @xr2/SOH /SOH /[email protected]/ @xrmˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ¤0 (6) for at least one choice of r1< r2</SOH /SOH /SOH< rminf1; 2; : : :; n g;then there are constants /NAK1; /NAK2;. . .; /NAKmsuch that X0is a critical point of f/NUL/NAK1g1/NUL/NAK2g2/NUL /SOH /SOH /SOH /NUL /NAKmgmI that is ; @f .X0/ @xi/NUL/[email protected]/ @xi/NUL/[email protected]/ @xi/NUL /SOH /SOH /SOH /NUL /[email protected]/ @xiD0; 1/DC4i/DC4n. The following implementation of this theorem is the method of Lagrange multipliers . (a) Find the critical points of f/NUL/NAK1g1/NUL/NAK2g2/NUL /SOH /SOH /SOH /NUL /NAKmgm; treating /NAK1,/NAK2, . . ./NAKmas unspecified constants. (b) Find /NAK1,/NAK2, . . . , /NAKmso that the critical points obtained in (a) satisfy the con- straints. (c) Determine which of the critical points are constrained extr eme points of f. This can usually be done by physical or intuitive arguments. Ifaandb1,b2, . . . , bmare nonzero constants and cis an arbitrary constant, then the local extreme points of fsubject to g1Dg2D /SOH /SOH /SOH D gmD0are the same as the local extreme points of af/NULcsubject to b1g1Db2g2D /SOH /SOH /SOH D bmgmD0. Therefore, we can replace f/NUL/NAK1g1/NUL/NAK2g2/NUL/SOH /SOH /SOH/NUL /NAKmgmbyaf/NUL/NAK1b1g1/NUL/NAK2b2g2/NUL/SOH /SOH /SOH/NUL /NAKmbmgm/NULc to simplify computations. (Usually, the “ /NULc” indicates dropping additive constants.) We will denote the final form by L(forLagrangian ). 3 3 Extrema subject to one constraint Here is Theorem 1withmD1. Theorem 2 Suppose that n > 1: IfX0is a local extreme point of fsubject to g.X/D 0andgxr.X0/¤0for some r2 f1; 2; : : :; n g;then there is a constant /NAKsuch that fxi.X0//NUL/NAKgxi.X0/D0; (7) 1/DC4i/DC4nIthus;X0is a critical point of f/NUL/NAKg: Proof For notational convenience, let rD1and denote UD.x2; x3; : : : x n/and U0D.x20; x30; : : : x n0/: Since gx1.X0/¤0, the Implicit Function Theorem (Corollary 6.4.2, p. 423) implies that there is a unique continuously differentiable functio nhDh.U/;defined on a neighborhood N/SUBRn/NUL1ofU0;such that .h.U/;U/2Dfor all U2N,h.U0/Dx10, and g.h.U/;U/D0; U2N: (8) Now define /NAKDfx1.X0/ gx1.X0/; (9) which is permissible, since gx1.X0/¤0. This implies ( 7) with iD1. Ifi > 1 , differentiating ( 8) with respect to xiyields @g.h. U/;U/ @[email protected]. U/;U/ @[email protected]/ @xiD0; U2N: (10) Also, @f .h. U/;U// @xiD@f .h. U/;U/ @xiC@f .h. U/;U/ @[email protected]/ @xi;U2N: (11) Since .h.U0/;U0/DX0, (10) implies that @g.X0/ @[email protected]/ @[email protected]/ @xiD0: (12) IfX0is a local extreme point of fsubject to g.X/D0, then U0is an unconstrained local extreme point of f .h. U/;U/; therefore, ( 11) implies that @f .X0/ @xiC@f .X0/ @[email protected]/ @xiD0: (13) Since a linear homogeneous system /DC4a b c d/NAK/DC4u v/NAK D/DC40 0/NAK 4 has a nontrivial solution if and only if ˇˇˇˇa b c dˇˇˇˇD0; (Theorem 6.1.15, p. 376) , (12) and ( 13) imply that ˇˇˇˇˇˇˇˇˇ@f .X0/ @xi@f .X0/ @x1 @g.X0/ @[email protected]/ @x1ˇˇˇˇˇˇˇˇˇD0;soˇˇˇˇˇˇˇˇˇ@f .X0/ @[email protected]/ @xi @f .X0/ @[email protected]/ @x1ˇˇˇˇˇˇˇˇˇD0; since the determinants of a matrix and its transpose are equa l. Therefore, the system 2 6664@f .X0/ @[email protected]/ @xi @f .X0/ @[email protected]/ @x13 7775/DC4u v/NAK D/DC40 0/NAK has a nontrivial solution (Theorem 6.1.15, p. 376) . Since gx1.X0/¤0,umust be nonzero in a nontrivial solution. Hence, we may assume that uD1, so 2 6664@f .X0/ @[email protected]/ @xi @f .X0/ @[email protected]/ @x13 7775/DC41 v/NAK D/DC40 0/NAK : (14) In particular, @f .X0/ @[email protected]/ @x1D0;so/NULvDfx1.X0/ gx1.X0/: Now ( 9) implies that /NULvD/NAK, and ( 14) becomes 2 6664@f .X0/ @[email protected]/ @xi @f .X0/ @[email protected]/ @x13 7775/DC41 /NUL/NAK/NAK D/DC40 0/NAK : Computing the topmost entry of the vector on the left yields ( 7). Example 1 Find the point .x0; y0/on the line axCbyDd closest to a given point .x1; y1/. 5 Solution We must minimizep .x/NULx1/2C.y/NULy1/2subject to the constraint. This is equivalent to minimizing .x/NULx1/2C.y/NULy1/2subject to the constraint, which is simpler. For, this we could let LD.x/NULx1/2C.y/NULy1/2/NUL/NAK.ax Cby/NULd/I however, LD.x/NULx1/2C.y/NULy1/2 2/NUL/NAK.ax Cby/ is better. Since LxDx/NULx1/NUL/NAKa and LyDy/NULy1/NUL/NAKb; .x0; y0/D.x1C/NAKa; y 1C/NAKb/, where we must choose /NAKso that ax0Cby0Dd. Therefore, ax0Cby0Dax1Cby1C/NAK.a2Cb2/Dd; so /NAKDd/NULax1/NULby1 a2Cb2; x0Dx1C.d/NULax1/NULby1/a a2Cb2;andy0Dy1C.d/NULax1/NULby1/b a2Cb2: The distance from .x1; y1/to the line is p .x0/NULx1/2C.y0/NULy1/2Djd/NULax1/NULby1jp a2Cb2: Example 2 Find the extreme values of f .x; y/ D2xCysubject to x2Cy2D4: Solution Let LD2xCy/NUL/NAK 2.x2Cy2/I then LxD2/NUL/NAKxandLyD1/NUL/NAKy; so.x0; y0/D.2=/NAK; 1=/NAK/ . Since x2 0Cy2 0D4,/NAKD ˙p 5=2. Hence, the constrained maximum is 2p 5, attained at .4=p 5; 2=p 5/, and the constrained minimum is /NUL2p 5, attained at ./NUL4=p 5;/NUL2=p 5/. Example 3 Find the point in the plane 3xC4yC´D1 (15) closest to ./NUL1; 1; 1/ . Solution We must minimize f .x; y; ´/ D.xC1/2C.y/NUL1/2C.´/NUL1/2 6 subject to ( 15). Let LD.xC1/2C.y/NUL1/2C.´/NUL1/2 2/NUL/NAK.3x C4yC´/I then LxDxC1/NUL3/NAK; L yDy/NUL1/NUL4/NAK; andL´D´/NUL1/NUL/NAK; so x0D /NUL1C3/NAK; y 0D1C4/NAK; ´ 0D1C/NAK: From ( 15), 3./NUL1C3/NAK/C4.1C4/NAK/C.1C/NAK//NUL1D1C26/NAKD0; so/NAKD /NUL1=26 and .x0; y0; ´0/D/DC2 /NUL29 26;22 26;25 26/DC3 : The distance from .x0; y0; ´0/to./NUL1; 1; 1/ is p .x0C1/2C.y0/NUL1/2C.´0/NUL1/2D1p 26: Example 4 Assume that n/NAK2andxi/NAK0,1/DC4i/DC4n. (a) Find the extreme values ofnX iD1xisubject tonX iD1x2 iD1. (b) Find the minimum value ofnX iD1x2 isubject tonX iD1xiD1. Solution (a) Let LDnX iD1xi/NUL/NAK 2nX iD1x2 iI then LxiD1/NUL/NAKxi;soxi0D1 /NAK; 1 /DC4i/DC4n: Hence,nX iD1x2 i0Dn=/NAK2, so/NAKD ˙pnand .x10; x20; : : : ; x n0/D ˙/DC21pn;1pn; : : : ;1pn/DC3 : Therefore, the constrained maximum ispnand the constrained minimum is /NULpn. Solution (b) Let LD1 2nX iD1x2 i/NUL/NAKnX iD1xiI 7 then LxiDxi/NUL/NAK;soxi0D/NAK; 1 /DC4i/DC4n: Hence,nX iD1xi0Dn/NAKD1, soxi0D/NAKD1=nand the constrained minimum is nX iD1x2 i0D1 n There is no constrained maximum. (Why?) Example 5 Show that x1=py1=q/DC4x pCy q; x; y /NAK0; if1 pC1 qD1; p > 0; andq > 0: (16) Solution We first find the maximum of f .x; y/ Dx1=py1=q subject tox pCy qD/ESC; x /NAK0; y /NAK0; (17) where /ESCis a fixed but arbitrary positive number. Since fis continuous, it must assume a maximum at some point .x0; y0/on the line segment ( 17), and .x0; y0/cannot be an endpoint of the segment, since f .p/ESC; 0/ Df .0; q/ESC/ D0. Therefore, .x0; y0/is in the open first quadrant. Let LDx1=py1=q/NUL/NAK/DC2x pCy q/DC3 : Then LxD1 pxf .x; y/ /NUL/NAK pandLyD1 qyf .x; y/ /NUL/NAK qD0; sox0Dy0Df .x 0; y0/=/NAK. Now( 16) and ( 17) imply that x0Dy0D/ESC. Therefore, f .x; y/ /DC4f ./ESC; /ESC/ D/ESC1=p/ESC1=qD/ESCDx pCy q: This can be generalized (Exercise 53). It can also be used to generalize Schwarz’s inequality (Exercise 54). 8 4 Constrained Extrema of Quadratic Forms In this section it is convenient to write XD2 6664x1 x2 ::: xn3 7775: Aneigenvalue of a square matrix ADŒaij/c141n i;jD1is a number /NAKsuch that the system AXD/NAKX; or, equivalently, .A/NUL/NAKI/XD0; has a solution X¤0. Such a solution is called an eigenvector ofA. You probably know from linear algebra that /NAKis an eigenvalue of Aif and only if det.A/NUL/NAKI/D0: Henceforth we assume that Ais symmetric .aijDaj i; 1/DC4i; j/DC4n/. In this case, det.A/NUL/NAKI/D./NUL1/n./NAK/NUL/NAK1/./NAK/NUL/NAK2//SOH /SOH /SOH./NAK/NUL/NAKn/; where /NAK1; /NAK2; : : : ; /NAK nare real numbers. The function Q.X/DnX i;jD1aijxixj is aquadratic form . To find its maximum or minimum subject tonX iD1x2 iD1, we form the Lagrangian LDQ.X//NUL/NAKnX iD1x2 i: Then LxiD2nX jD1aijxj/NUL2/NAKx iD0; 1 /DC4i/DC4n; so nX jD1aijxj 0D/NAKxi0; 1 /DC4i/DC4n: Therefore, X0is a constrained critical point of Qsubject tonX iD1x2 iD1if and only ifAX0D/NAKX0for some /NAK; that is, if and only if /NAKis an eigenvalue and X0is an 9 associated unit eigenvector of A. IfAX0DX0andnX ix2 i0D1, then Q.X0/DnX iD10 @nX jD1aijxj 01 Axi0DnX iD1./NAKx i0/xi0 D/NAKnX iD1x2 i0D/NAKI therefore, the largest and smallest eigenvalues of Aare the maximum and minimum values of Qsubject tonX iD1x2 iD1. Example 6 Find the maximum and minimum values Q.X/Dx2Cy2C2´2/NUL2xyC4x´C4y´ subject to the constraint x2Cy2C´2D1: (18) Solution The matrix of Qis AD2 41/NUL1 2 /NUL1 1 2 2 2 23 5 and det.A/NUL/NAKI/Dˇˇˇˇˇˇ1/NUL/NAK /NUL1 2 /NUL1 1 /NUL/NAK 2 2 2 2 /NUL/NAKˇˇˇˇˇˇ D /NUL ./NAKC2/./NAK/NUL2/./NAK/NUL4/; so /NAK1D4; /NAK 2D2; /NAK 3D /NUL2 are the eigenvalues of A. Hence, /NAK1D4and/NAK3D /NUL2are the maximum and minimum values of Qsubject to ( 18). To find the points .x1; y1; ´1/where Qattains its constrained maximum, we first find an eigenvector of Acorresponding to /NAK1D4. To do this, we find a nontrivial solution of the system .A/NUL4I/2 4x1 y1 ´13 5D2 4/NUL3/NUL1 2 /NUL1/NUL3 2 2 2 /NUL23 52 4x1 y1 ´13 5D2 40 0 03 5: 10 All such solutions are multiples of2 41 1 23 5:Normalizing this to satisfy ( 18) yields X1D1p 62 4x1 y1 ´13 5D ˙2 41 1 13 5: To find the points .x3; y3; ´3/where Qattains its constrained minimum, we first find an eigenvector of Acorresponding to /NAK3D /NUL2. To do this, we find a nontrivial solution of the system .AC2I/2 4x3 y3 ´33 5D2 43/NUL1 2 /NUL1 3 2 2 2 43 52 4x3 y3 ´33 5D2 40 0 03 5: All such solutions are multiples of2 41 1 /NUL13 5:Normalizing this to satisfy ( 18) yields X3D2 4x2 y2 ´23 5D ˙1p 32 41 1 /NUL13 5: As for the eigenvalue /NAK2D2, we leave it you to verify that the only unit vectors that satisfy AX2D2X2are X2D ˙1p 22 41 1 /NUL13 5: For more on this subject, see Theorem 4. 5 Extrema subject to two constraints Here is Theorem 1withmD2. Theorem 3 Suppose that n > 2: IfX0is a local extreme point of fsubject to g1.X/D g2.X/D0andˇˇˇˇˇˇˇˇˇ@g1.X0/ @[email protected]/ @xs @g2.X0/ @[email protected]/ @xsˇˇˇˇˇˇˇˇˇ¤0 (19) for some randsinf1; 2; : : :; n g;then there are constants /NAKand/SYNsuch that @f .X0/ @xi/NUL/[email protected]/ @xi/NUL/[email protected]/ @xiD0; (20) 1/DC4i/DC4n. 11 Proof For notational convenience, let rD1andsD2. Denote UD.x3; x4; : : : x n/and U0D.x30; x30; : : : x n0/: Since ˇˇˇˇˇˇˇˇˇ@g1.X0/ @[email protected]/ @x2 @g2.X0/ @[email protected]/ @x2ˇˇˇˇˇˇˇˇˇ¤0; (21) the Implicit Function Theorem (Theorem 6.4.1, p. 420) implies that there are unique continuously differentiable functions h1Dh1.x3; x4; : : : ; x n/andh2Dh1.x3; x4; : : : ; x n/; defined on a neighborhood N/SUBRn/NUL2ofU0;such that .h1.U/; h2.U/;U/2Dfor all U2N,h1.U0/Dx10,h2.U0/Dx20, and g1.h1.U/; h2.U/;U/Dg2.h1.U/; h2.U/;U/D0; U2N: (22) From ( 21), the system 2 [email protected]/ @[email protected]/ @x2 @g2.X0/ @[email protected]/ @x23 7775/DC4/NAK /SYN/NAK D/DC4fx1.X0/ fx2.X0//NAK (23) has a unique solution (Theorem 6.1.13, p. 373) . This implies ( 20) with iD1and iD2. If3/DC4i/DC4n, then differentiating ( 22) with respect to xiand recalling that .h1.U0/; h2.U0/;U0/DX0yields @g1.X0/ @[email protected]/ @[email protected]/ @[email protected]/ @[email protected]/ @xiD0 and @g2.X0/ @[email protected]/ @[email protected]/ @[email protected]/ @[email protected]/ @xiD0: IfX0is a local extreme point of fsubject to g1.X/Dg2.X/D0, then U0is an unconstrained local extreme point of f .h 1.U/; h2.U/;U/; therefore, @f .X0/ @xiC@f .X0/ @[email protected]/ @xiC@f .X0/ @[email protected]/ @xiD0: The last three equations imply that ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@f .X0/ @xi@f .X0/ @x1@f .X0/ @x2 @g1.X0/ @[email protected]/ @[email protected]/ @x2 @g2.X0/ @[email protected]/ @[email protected]/ @x2ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇD0; 12 ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@f .X0/ @[email protected]/ @[email protected]/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x2ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇD0: Therefore, there are constants c1,c2,c3, not all zero, such that 2 666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x23 7777777777752 4c1 c2 c33 5D2 40 0 03 5: (24) Ifc1D0, then2 [email protected]/ @[email protected]/ @x2 @g2.X0/ @[email protected]/ @x23 7775/DC4c2 c3/NAK D/DC40 0/NAK ; so (19) implies that c2Dc3D0; hence, we may assume that c1D1in a nontrivial solution of ( 24). Therefore, 2 666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x23 7777777777752 41 c2 c33 5D2 40 0 03 5; (25) which implies that 2 [email protected]/ @[email protected]/ @x2 @g2.X0/ @[email protected]/ @x23 7775/DC4/NULc2 /NULc3/NAK D/DC4fx1.X0/ fx2.X0//NAK : 13 Since ( 23) has only one solution, this implies that c2D /NUL/NAKandc2D /NUL/SYN, so ( 25) becomes 2 666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x23 7777777777752 41 /NUL/NAK /NUL/SYN3 5D2 40 0 03 5: Computing the topmost entry of the vector on the left yields ( 20). Example 7 Minimize f .x; y; ´; w/ Dx2Cy2C´2Cw2 subject to xCyC´CwD10andx/NULyC´C3wD6: (26) Solution Let LDx2Cy2C´2Cw2 2/NUL/NAK.xCyC´Cw//NUL/SYN.x/NULyC´C3w/I then LxDx/NUL/NAK/NUL/SYN LyDy/NUL/NAKC/SYN L´D´/NUL/NAK/NUL/SYN LwDw/NUL/NAK/NUL3/SYN; so x0D/NAKC/SYN; y 0D/NAK/NUL/SYN; ´ 0D/NAKC/SYN; w 0D/NAKC3/SYN: (27) This and ( 26) imply that ./NAKC/SYN/C./NAK/NUL/SYN/C./NAKC/SYN/C./NAKC3/SYN/ D10 ./NAKC/SYN//NUL./NAK/NUL/SYN/C./NAKC/SYN/C.3/NAKC9/SYN/ D 6: Therefore, 4/NAKC4/SYN D10 4/NAKC12/SYN D 6; so/NAKD3and/SYND /NUL1=2. Now ( 27) implies that .x0; y0; ´0; w0/D/DC25 2;7 2;5 23 2/DC3 : 14 Since f .x; y; ´; w/ is the square of the distance from .x; y; ´; w/ to the origin, it attains a minimum value (but not a maximum value) subject to the const raints; hence the constrained minimum value is f/DC25 2;7 2;5 2;3 2/DC3 D27: Example 8 The distance between two curves in R2is the minimum value of p .x1/NULx2/2C.y1/NULy2/2; where .x1; y1/is on one curve and .x2; y2/is on the other. Find the distance between the ellipse x2C2y2D1 and the line xCyD4: (28) Solution We must minimize d2D.x1/NULx2/2C.y1/NULy2/2 subject to x2 1C2y2 1D1andx2Cy2D4: Let LD.x1/NULx2/2C.y1/NULy2/2/NUL/NAK.x2 1C2y2 1/ 2/NUL/SYN.x 2Cy2/I then Lx1Dx1/NULx2/NUL/NAKx1 Ly1Dy1/NULy2/NUL2/NAKy 1 Lx2Dx2/NULx1/NUL/SYN Ly2Dy2/NULy1/NUL/SYN; so x10/NULx20D/NAKx10 (i) y10/NULy20D2/NAKy 10 (ii) x20/NULx10D/SYN (iii) y20/NULy10D/SYN: (iv) From (i) and (iii), /SYND /NUL/NAKx10; from (ii) and (iv), /SYND /NUL2/NAKy 10. Since the curves do not intersect, /NAK¤0, sox10D2y10. Since x2 10C2y2 10D1and.x0; y0/is in the first quadrant, .x10; y10/D/DC22p 6;1p 6/DC3 : (29) 15 Now (iii), (iv), and ( 28) yield the simultaneous system x20/NULy20Dx10/NULy10D1p 6; x 20Cy20D4; so .x20; y20/D/DC2 2C1 2p 6; 2/NUL1 2p 6/DC3 : From this and ( 29), the distance between the curves is "/DC2 2C1 2p 6/NUL2p 6/DC32 C/DC2 2/NUL1 2p 6/NUL1p 6/DC32#1=2 Dp 2/DC2 2/NUL3 2p 6/DC3 : 6 Proof of Theorem 1 Proof For notational convenience, let r`D`,1/DC4`/DC4m, so ( 6) becomes ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@g1.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm @g2.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm:::::::::::: @gm.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xmˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ¤0 (30) Denote UD.xmC1; xmC2; : : : x n/and U0D.xmC1;0; xmC2;0; : : : x n0/: From ( 30), the Implicit Function Theorem implies that there are uniq ue continuously differentiable functions h`Dh`.U/,1/DC4`/DC4m, defined on a neighborhood NofU0, such that .h1.U/; h2.U/; : : : ; h m.U/;U/2D;for all U2N; .h1.U0/; h2.U0/; : : : ; h m.U0/;U0/DX0; (31) and g`.h1.U/; h2.U/; : : : ; h m.U/;U/D0; U2N; 1 /DC4`/DC4m: (32) Again from ( 30), the system 2 [email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm @g2.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm:::::::::::: @gm.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm3 77777777777752 6664/NAK1 /NAK2 ::: /NAKm3 7775D2 6664fx1.X0/ fx2.X0/ ::: fxm.X0/3 7775(33) 16 has a unique solution. This implies that @f .X0/ @xi/NUL/[email protected]/ @xi/NUL/[email protected]/ @xi/NUL /SOH /SOH /SOH /NUL /[email protected]/ @xiD0 (34) for1/DC4i/DC4m. IfmC1/DC4i/DC4n, differentiating ( 32) with respect to xiand recalling ( 31) yields @g`.X0/ @xiCmX jD1@g`.X0/ @[email protected]/ @xiD0; 1 /DC4`/DC4m: IfX0is local extreme point fsubject to g1.X/Dg2.X/D /SOH /SOH /SOH D gm.X/D0, then U0 is an unconstrained local extreme point of f .h 1.U/; h2.U/; : : : h m.U/;U/; therefore, @f .X0/ @xiCmX jD1@f .X0/ @[email protected]/ @xiD0: The last two equations imply that ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@f .X0/ @xi@f .X0/ @x1@f .X0/ @x2/SOH /SOH /SOH@f .X0/ @xm @g1.X0/ @[email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm @g2.X0/ @[email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm::::::::::::::: @gm.X0/ @[email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xmˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇD0; so ˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇ@f .X0/ @[email protected]/ @[email protected]/ @xi: : :@gm.X0/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1: : :@gm.X0/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x2: : :@gm.X0/ @x2::::::::::::::: @f .X0/ @[email protected]/ @[email protected]/ @xm: : :@gm.X0/ @xmˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇˇD0: 17 Therefore, there are constant c0,c1, . . .cm, not all zero, such that 2 66666666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi: : :@gm.X0/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1: : :@gm.X0/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x2: : :@gm.X0/ @x2::::::::::::::: @f .X0/ @[email protected]/ @[email protected]/ @xm: : :@gm.X0/ @xm3 777777777777777752 666664c0 c1 c3 ::: cm3 777775D2 6666640 0 0 ::: 03 777775:(35) Ifc0D0, then 2 [email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm @g2.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm:::::::::::: @gm.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm3 77777777777752 6664c1 c2 ::: cm3 7775D2 66640 0 ::: 03 7775 and ( 30) implies that c1Dc2D /SOH /SOH /SOH D cmD0; hence, we may assume that c0D1in a nontrivial solution of ( 35). Therefore, 2 66666666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi: : :@gm.X0/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1: : :@gm.X0/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x2: : :@gm.X0/ @x2::::::::::::::: @f .X0/ @[email protected]/ @[email protected]/ @xm: : :@gm.X0/ @xm3 777777777777777752 6666641 c1 c2 ::: cm3 777775D2 6666640 0 0 ::: 03 777775;(36) 18 which implies that 2 [email protected]/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm @g2.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm:::::::::::: @gm.X0/ @[email protected]/ @x2/SOH /SOH /[email protected]/ @xm3 77777777777752 6664/NULc1 /NULc2 ::: /NULcm3 7775D2 6664fx1.X0/ fx2.X0/ ::: fxm.X0/3 7775 Since ( 33) has only one solution, this implies that cjD /NUL/NAKj,1/DC4j/DC4n, so ( 36) becomes 2 66666666666666664@f .X0/ @[email protected]/ @[email protected]/ @xi: : :@gm.X0/ @xi @f .X0/ @[email protected]/ @[email protected]/ @x1: : :@gm.X0/ @x1 @f .X0/ @[email protected]/ @[email protected]/ @x2: : :@gm.X0/ @x2::::::::::::::: @f .X0/ @[email protected]/ @[email protected]/ @xm: : :@gm.X0/ @xm3 777777777777777752 6666641 /NUL/NAK1 /NUL/NAK2 ::: /NUL/NAKm3 777775D2 6666640 0 0 ::: 03 777775: Computing the topmost entry of the vector on the left yields y ields ( 34), which com- pletes the proof. Example 9 MinimizenX iD1x2 isubject to nX iD1arixiDcr; 1 /DC4r/DC4m; (37) where nX iD1ariasiD( 1ifrDs; 0ifr¤s:(38) Solution Let LD1 2nX iD1x2 i/NULmX sD1/NAKsnX iD1asixi: Then LxiDxi/NULmX sD1/NAKsasi; 1 /DC4i/DC4n; 19 so xi0DmX sD1/NAKsasi1/DC4i/DC4n; (39) and arixi0DmX sD1/NAKsariasi: Now ( 38) implies that nX iD1arixi0DmX sD1/NAKsnX iD1ariasiD/NAKr: From this and ( 37),/NAKrDcr,1/DC4r/DC4m, and ( 39) implies that xi0DmX sD1csasi; 1 /DC4i/DC4n: Therefore, x2 i0DmX r;sD1crcsariasi; 1 /DC4i/DC4n; and ( 38) implies that nX iD1x2 i0DmX r;sD1crcsnX iD1ariasiDmX rD1c2 r: The next theorem provides further information on the relati onship between the eigenvalues of a symmetric matrix and constrained extrema o f its quadratic form. It can be proved by successive applications of Theorem 1; however, we omit the proof. Theorem 4 Suppose that ADŒars/c141n r;sD12Rn/STXnis symmetric and let Q.x/DnX r;sD1arsxrxs: Suppose also that x1D2 6664x11 x21 ::: xn13 7775 minimizes Qsubject toPn iD1x2 i. For 2/DC4r/DC4n, suppose that xrD2 6664x1r x2r ::: xnr3 7775; 20 minimizes Qsubject to nX iD1x2 iD1andnX iD1xisxiD0; 1 /DC4s/DC4r/NUL1: Denote /NAKrDnX i;jD1aijxirxjr; 1 /DC4r/DC4n: Then /NAK1/DC4/NAK2/DC4 /SOH /SOH /SOH /DC4 /NAKnandAxrD/NAKrxr; 1 /DC4r/DC4n: 21 7 Exercises 1. Find the point on the plane 2xC3yC´D7closest to .1;/NUL2; 3/ . 2. Find the extreme values of f .x; y/ D2xCysubject to x2Cy2D5. 3. Suppose that a; b > 0 anda˛2Cbˇ2D1. Find the extreme values of f .x; y/ DˇxC˛ysubject to ax2Cby2D1. 4. Find the points on the circle x2Cy2D320closest to and farthest from .2; 4/ . 5. Find the extreme values of f .x; y; ´/ D2xC3yC´subject to x2C2y2C3´2D1: 6. Find the maximum value of f .x; y/ Dxyon the line axCbyD1, where a; b > 0 . 7. A rectangle has perimeter p. Find its largest possible area. 8. A rectangle has area A. Find its smallest possible perimeter. 9. A closed rectangular box has surface area A. Find it largest possible volume. 10. The sides and bottom of a rectangular box have total area A. Find its largest possible volume. 11. A rectangular box with no top has volume V. Find its smallest possible surface area. 12. Maximize f .x; y; ´/ Dxy´ subject to x aCy bC´ cD1; where a,b,c > 0 . 13. Two vertices of a triangle are ./NULa; 0/ and.a; 0/ , and the third is on the ellipse x2 a2Cy2 b2D1: Find its largest possible area. 14. Show that the triangle with the greatest possible area for a g iven perimeter is equilateral, given that the area of a triangle with sides x,y,´and perimeter sis ADp s.s/NULx/.s/NULy/.s/NUL´/: 22 15. A box with sides parallel to the coordinate planes has its ver tices on the ellipsoid x2 a2Cy2 b2C´2 c2D1: Find its largest possible volume. 16. Derive a formula for the distance from .x1; y1; ´1/to the plane axCbyCc´D/ESC: 17. LetXiD.xi; yi; ´i/,1/DC4i/DC4n. Find the point in the plane axCbyCc´D/ESC for whichPn iD1jX/NULXij2is a minimum. Assume that none of the Xiare in the plane. 18. Find the extreme values of f .X/DnX iD1.xi/NULci/2subject tonX iD1x2 iD1. 19. Find the extreme values of f .x; y; ´/ D2xyC2x´C2y´ subject to x2Cy2C´2D1: 20. Find the extreme values of f .x; y; ´/ D3x2C2y2C3´2C2x´ subject to x2Cy2C´2D1: 21. Find the extreme values of f .x; y/ Dx2C8xyC4y2subject to x2C2xyC4y2D1: 22. Find the extreme value of f .x; y/ D˛Cˇxy subject to .axCby/2D1. Assume that ab¤0. 23. Find the extreme values of f .x; y; ´/ DxCy2C2´subject to 4x2C9y2/NUL36´2D36: 24. Find the extreme values of f .x; y; ´; w/ D.xC´/.y Cw/subject to x2Cy2C´2Cw2D1: 25. Find the extreme values of f .x; y; ´; w/ D.xC´/.y Cw/subject to x2Cy2D1and ´2Cw2D1: 23 26. Find the extreme values of f .x; y; ´; w/ D.xC´/.y Cw/subject to x2C´2D1and y2Cw2D1: 27. Find the distance between the circle x2Cy2D1the hyperbola xyD1. 28. Minimize f .x; y; x/ Dx2 ˛2Cy2 ˇ2C´2 /CR2subject to axCbyCc´Ddandx, y,´ > 0 . 29. Find the distance from .c1; c2; : : : ; c n/to the plane a1x1Ca2x2C /SOH /SOH /SOH C anxnDd: 30. Find the maximum value of f .X/DnX iD1aix2 isubject tonX iD1bix4 iD1, where p; q > 0 andai,bixi> 0,1/DC4i/DC4n. 31. Find the extreme value of f .X/DnX iD1aixp isubject tonX iD1bixq iD1, where p, q>0 and ai,bi,xi> 0,1/DC4i/DC4n. 32. Find the minimum value of f .x; y; ´; w/ Dx2C2y2C´2Cw2 subject to xCyC´C3w D1 xCyC2´CwD2: 33. Find the minimum value of f .x; y; ´/ Dx2 a2Cy2 b2C´2 c2 subject to p1xCp2yCp3´Dd, assuming that at least one of p1,p2,p3is nonzero. 34. Find the extreme values of f .x; y; ´/ Dp1xCp2yCp3´subject to x2 a2Cy2 b2C´2 c2D1; assuming that at least one of p1,p2,p3is nonzero. 35. Find the distance from ./NUL1; 2; 3/ to the intersection of the planes xC2y/NUL3´D4and2x/NULyC2´D5. 24 36. Find the extreme values of f .x; y; ´/ D2xCyC2´subject to x2Cy2D4 andxC´D2. 37. Find the distance between the parabola yD1Cx2and the line xCyD /NUL1. 38. Find the distance between the ellipsoid 3x2C9y2C6´2D10 and the plane 3xC3yC6´D70: 39. Show that the extreme values of f .x; y; ´/ DxyCy´C´xsubject to x2 a2Cy2 b2C´2 c2D1 are the largest and smallest eigenvalues of the matrix 2 40 a2a2 b20 b2 c2c203 5: 40. Show that the extreme values of f .x; y; ´/ DxyC2y´C2´x subject to x2 a2Cy2 b2C´2 c2D1 are the largest and smallest eigenvalues of the matrix 2 40 a2=2 a2 b2=2 0 b2 c2c203 5: 41. Find the extreme values of x.yC´/subject to x2 a2Cy2 b2C´2 c2D1: 42. Leta,b,c,p,q,r,˛,ˇ, and /CRbe positive constants. Find the maximum value off .x; y; ´/ Dx˛yˇ´/CRsubject to axpCbyqCc´rD1andx; y; ´ > 0: 43. Find the extreme values of f .x; y; ´; w/ Dxw/NULy´ subject to x2C2y2D4and 2´2Cw2D9: 25 44. Leta,b,c,anddbe positive. Find the extreme values of f .x; y; ´; w/ Dxw/NULy´ subject to ax2Cby2D1; c´2Cdw2D1; if(a)ad¤bc;(b)adDbc: 45. Minimize f .x; y; ´/ D˛x2Cˇy2C/CR´2subject to a1xCa2yCa3´Dcandb1xCb2yCb3´Dd: Assume that ˛; ˇ; /CR > 0; a2 1Ca2 2Ca2 3¤0;andb2 1Cb2 2Cb2 3¤0: Formulate and apply a required additional assumption. 46. Minimize f .X;Y/DnX iD1.xi/NUL˛i/2subject to nX iD1aixiDcandnX iD1bixiDd; wherenX iD1a2 iDnX iD1b2 iD1andnX iD1aibiD0: 47. Find.x10;x 20; : : : ; x n0/to minimize Q.X/DnX iD1x2 i subject to nX iD1xiD1andnX iD1ixiD0: Prove explicitly that if nX jD1yiD1;nX iD1iyiD0 andyi¤xi0for some i2 f1; 2; : : :; n g, then nX iD1y2 i>nX iD1x2 i0: 26 48. Letp1,p2, . . . , pnandsbe positive numbers. Maximize f .X/D.s/NULx1/p1.s/NULx2/p2/SOH /SOH /SOH.s/NULxn/pn subject to x1Cx2C /SOH /SOH /SOH C xnDs. 49. Maximize f .X/Dxp1 1xp2 2/SOH /SOH /SOHxpnnsubject to xi> 0,1/DC4i/DC4n, and nX iD1xi /ESCiDS; where p1,p2,. . . ,pn,/ESC1,/ESC2, . . . , /ESCn, and Vare given positive numbers. 50. Maximize f .X/DnX iD1xi /ESCi subject to xi> 0,1/DC4i/DC4n, and xp1 1xp2 2/SOH /SOH /SOHxpn nDV; where p1,p2,. . . ,pn,/ESC1,/ESC2, . . . , /ESCn, and Sare given positive numbers. 51. Suppose that ˛1,˛2, . . .˛nare positive and at least one of a1,a2, . . . , anis nonzero. Let .c1; c2; : : : ; c n/be given. Minimize Q.X/DnX iD1.xi/NULci/2 ˛i subject to a1x1Ca2x2C /SOH /SOH /SOH C anxnDd: 52. Schwarz’s inequality says that .a1; a2; : : : ; a n/and.x1; x2; : : : ; x n/are arbi- trary n-tuples of real numbers, then ja1x1Ca2x2C /SOH /SOH /SOHC anxnj /DC4.a2 1Ca2 2C /SOH /SOH /SOHC a2 n/1=2.x2 1Cx2 2C /SOH /SOH /SOHC x2 n/1=2: Prove this by finding the extreme values of f .X/DnX iD1aixisubject tonX iD1x2 iD/ESC2. 53. Letx1,x2, . . . , xm,r1,r2, . . . , rmbe positive and r1Cr2C /SOH /SOH /SOH C rmDr: Show that/NULxr1 1xr2 2/SOH /SOH /SOHxrm m/SOH1=r/DC4r1x1Cr2x2C /SOH /SOH /SOH rmxm r; and give necessary and sufficient conditions for equality. ( Hint: Maximize xr1 1xr2 2/SOH /SOH /SOHxrmmsubject toPm jD1rjxjD/ESC > 0 ,x1> 0,x2> 0, . . . , xm> 0.) 27 54. LetADŒaij/c141be an m/STXnmatrix. Suppose that p1,p2, . . . , pm> 0and mX jD11 pjD1; and define /ESCiDnX jD1jaijjpi; 1 /DC4i/DC4m: Use Exercise 53to show that ˇˇˇˇˇˇnX jD1aija2j/SOH /SOH /SOHamjˇˇˇˇˇˇ/DC4/ESC1=p 1 1/ESC1=p 2 2/SOH /SOH /SOH/ESC1=p m m: (With mD2this is Hölder’s inequality , which reduces to Schwarz’s inequality ifp1Dp2D2.) 55. Letc0,c1, . . . , cmbe given constants and n/NAKmC1. Show that the minimum value of Q.X/DnX rD0x2 r subject to nX rD0xrrsDcs; 0 /DC4s/DC4m; is attained when xrDmX sD0/NAKsrs; 0 /DC4r/DC4n; where mX `D0/ESCsC`/NAK`Dcsand/ESCsDnX rD0rs; 0 /DC4s/DC4m: Show that if fxrgn rD0satisfies the constraints and xr¤xr0for some r, then nX rD0x2 r>nX rD0x2 r0: 56. Suppose that n > 2k . Show that the minimum value of f .W/DnX iD/NULnw2 i, subject to the constraint nX iD/NULnwiP.r/NULi/DP.r/ 28 whenever ris an integer and Pis a polynomial of degree /DC42k, is attained with wi0D2kX rD0/NAKrir; 1 /DC4i/DC4n; where 2kX rD0/NAKr/ESCrCsD( 1ifsD0; 0if1/DC4s/DC42k;and/ESCsDnX jD/NULnjs: Show that if fwign iD/NULnsatisfies the constraint and wi¤wi0for some i, then nX iD/NULnw2 i>nX iD/NULnw2 i0: 57. Suppose that n/NAKk. Show that the minimum value of fnX iD0w2 i, subject to the constraintnX iD0wiP.r/NULi/DP.rC1/ whenever ris an integer and Pis a polynomial of degree /DC4k, is attained with wi0DkX rD0/NAKrir; 0 /DC4i/DC4n; where kX rD0/ESCrCs/NAKrD./NUL1/s; 0 /DC4s/DC4k; and /ESC`DnX iD0i`; 0 /DC4`/DC42k: Show that ifnX iD0uiP.r/NULi/DP.rC1/ whenever ris an integer and Pis a polynomial of degree /DC4k, and ui¤wi0 for some i, then nX iD0u2 i>nX iD0w2 i0: 58. Minimize f .X/DnX iD1.xi/NULci/2 ˛i subject to nX iD1airxiDdr; 1 /DC4r/DC4m 29 Assume that m > 1 ,˛1,˛2, . . .˛m> 0, and nX iD1˛iairaisD( 1ifrDs; 0ifr¤s: 30 8 Answers to selected exercises 1./NUL15 7/NUL2 7;25 7/SOH 2.˙53.1=p ab,/NUL1=p ab 4..8; 16/ is closest, ./NUL8;/NUL16/is farthest. 5.˙p 53=6 6.1=4ab 7.p2=4 8.4p A 9.A3=2=6p 610.A3=2=6p 311.3.2V /2=312.abc=27 13.ab 15.8abc=3p 3 18..1/NUL/SYN/2and.1C/SYN/2, where /SYND0 @nX jD1c2 j1 A1=2 19./NUL1,220.2,4 21./NUL2=3,222.˛˙ jˇj=4jabj23./NULp 5,73=16 24.˙125.˙2 26.˙227.p 2/NUL128.d2 .a˛/2C.bˇ2/C.c/CR/2 29.jd/NULa1c1/NULa2c2/NUL /SOH /SOH /SOH /NUL ancn/aijq a2 1Ca2 2C /SOH /SOH /SOH a2n30. nX iD1a2 i bi!1=2 31. nX iD1aq=.q /NULp/ ibp=.p /NULq/ i!1/NULp=q is a constrained maximum if p < q , a constrained minimum if p > q 32.689=845 33.d2 p2 1a2Cp2 2b2Cp2 3c234.˙.p2 1a2Cp2 2b2Cp2 3c2/1=2 35.p 693=45 36.2,637.7=4p 238.10p 6=3 41.˙jcjp a2Cb2=2 42.˛ˇ/CR pqr/DC2˛ pCˇ qC/CR r/DC3/NUL3 43.˙344. (a)˙1=p bc(b)˙1=p adD ˙1=p bc 46. c/NULnX iD1ai˛i!2 C d/NULnX iD1bi˛i!2 47.xi0D.4nC2/NUL6i/=n.n /NUL1/ 48.h .n/NUL1/s PiP pp1 1pp2 2/SOH /SOH /SOHppnn 49./DC2S p1Cp2C /SOH /SOH /SOH C pn/DC3p1Cp2C/SOH/SOH/SOHC pn .p1/ESC1/p1.p2/ESC2/p2/SOH /SOH /SOH.pn/ESCn/pn 50..p1Cp2C /SOH /SOH /SOH C pn//DC2V ./ESC1p1/p1./ESC2p2/p2/SOH /SOH /SOH./ESCnpn/pn/DC3 1 p1Cp2C/SOH/SOH/SOHC pn 51. d/NULnX iD1aici! /2= nX iD1a2 i˛i! 52.˙ nX iD1a2 i!1=2 nX iD1x2 i0!1=2 58.mX rD1 dr/NULnX iD1airci!2 31