Články

2.11E: Cvičenie pre Lagrangeových multiplikátorov


V cvičeniach 1-15 použite metódu Lagrangeových multiplikátorov na nájdenie maximálnych a minimálnych hodnôt funkcie, ktorá je predmetom daného obmedzenia.

1) Objektívna funkcia: (f (x, y) = 4xy ) Obmedzenie: ( frac {x ^ 2} {9} + frac {y ^ 2} {16} = 1 )

Odpoveď:
S výhradou daného obmedzenia má funkcia (f ) relatívne minimum (- 24 ) na oboch ( left (- frac {3 sqrt {2}} {2}, 2 sqrt { 2} right) ) a ( left ( frac {3 sqrt {2}} {2}, -2 sqrt {2} right) ) a relatívne maximum (24 ) na obaja ( left ( frac {3 sqrt {2}} {2}, 2 sqrt {2} right) ) a ( left (- frac {3 sqrt {2}} {2) }, -2 sqrt {2} vpravo) )

2) Objektívna funkcia: (f (x, y) = x ^ 2y ) Obmedzenie: (x ^ 2 + 2y ^ 2 = 6 )

3) Objektívna funkcia: (f (x, y) = x ^ 2 + y ^ 2 + 2x − 2y + 1 ) Obmedzenie: (g (x, y) = x ^ 2 + y ^ 2 = 2 ) )

Odpoveď:
S výhradou daného obmedzenia má (f ) relatívne minimum (- 1 ) pri ((-1, 1) ) a relatívne maximum (7 ) pri ((1, - 1) ).

4) Objektívna funkcia: (f (x, y) = xy ) Obmedzenie: (4x ^ 2 + 8y ^ 2 = 16 )

5) Objektívna funkcia: (f (x, y) = x ^ 2 + y ^ 2 ) Obmedzenie: (xy = 1 )

Odpoveď:
(f ) má relatívne minimum (2 ) v obidvoch ((-1, -1) ) a ((1,1) ), s výhradou daného obmedzenia.

6) Objektívna funkcia: (f (x, y) = x ^ 2 - y ^ 2 ) Obmedzenie: (x − 2y + 6 = 0 )

7) Objektívna funkcia: (f (x, y) = x ^ 2 + y ^ 2 ) Obmedzenie: (x + 2y − 5 = 0 )

Odpoveď:
S výhradou daného obmedzenia má (f ) v bode ((1, 2) ) relatívne minimum (f (1,2) = 5 ).

8) Objektívna funkcia: (f (x, y) = x ^ 2 + y ^ 2 ) Obmedzenie: ((x − 1) ^ 2 + 4y ^ 2 = 4 )

9) Objektívna funkcia: (f (x, y) = 4x ^ 3 + y ^ 2 ) Obmedzenie: (2x ^ 2 + y ^ 2 = 1 )

Odpoveď:
S výhradou daného obmedzenia má funkcia (f ) relatívne minimum (- sqrt {2} ) na ( left (- frac { sqrt {2}} {2}, 0 ) správny) ),
relatívne minimum ( frac {25} {27} ) v oboch bodoch ( doľava ( frac {1} {3}, - frac { sqrt {7}} {3} doprava) ) a ( dolava ( frac {1} {3}, frac { sqrt {7}} {3} doprava) ),
relatívne maximum ( sqrt {2} ) na ( left ( frac { sqrt {2}} {2}, 0 right) ) a relatívne maximum (1 ) na oba body ((0,1) ) a ((0, -1) ).
Riešenie:
Nech (g (x, y) = 2x ^ 2 + y ^ 2 ) je obmedzujúca funkcia. Potom:

( vecs nabla f (x, y) = 12x ^ 2 , hat { mathbf i} + 2y , hat { mathbf j} ) a ( vecs nabla g (x, y) ) = 4x , hat { mathbf i} + 2r , hat { mathbf j} )

Pomocou Lagrangeovej multiplikátorovej rovnice, [ vecs nabla f (x, y) = lambda vecs nabla g (x, y), nonumber ]
máme: [12x ^ 2 , hat { mathbf i} + 2y , hat { mathbf j} = 4x lambda , hat { mathbf i} + 2y lambda , hat { mathbf j} nonumber ]
čo nám dáva sústavu rovníc: [12x ^ 2 = 4x lambda, quad 2y = 2y lambda, quad text {a obmedzenie} quad 2x ^ 2 + y ^ 2 = 1 nonumber ]
Prepísaním prvých dvoch rovníc ako nulových produktov (prechodom na jednu stranu a faktoringom) dostaneme:
[ begin {align *} 4x (3x - lambda) & = 0 & text {and} && 2y (1 - lambda) & = 0 x = 0 quad text {or} quad lambda & = 3x & & & y = 0 quad text {alebo} quad lambda & = 1 end {zarovnať *} ]
Teraz zvážime kombinácie týchto riešení vyššie uvedených dvoch rovníc a zapojíme každé z nich do obmedzovacej rovnice, aby sme ich vyriešili pre zodpovedajúce Lagrangeove body.

Kombinácia (x = 0 ) a (y = 0 ) vytvára rozpor, ak je umiestnená do väzbovej rovnice, pretože tento bod nie je na elipsy.

Ak vezmeme kombináciu (x = 0 ) a ( lambda = 1 ), dáme (0 ) do obmedzenia (x ) v obmedzení a vyriešime pre (y ), pričom dostaneme: ( y = pm 1 ). To nám dáva dva Lagrangeove body: ((0, 1) ) a ((0, -1) ).

Ak vezmeme kombináciu ( lambda = 3x ) a (y = 0 ), dáme do obmedzenia (0 ) pre (y ) a vyriešime pre (x ), čím dostaneme: ( x = pm frac { sqrt {2}} {2} ). Toto nám dáva dva Lagrangeove body: ( left (- frac { sqrt {2}} {2}, 0 right) ) a ( left ( frac { sqrt {2}} {2}) , 0 vpravo) ).

Ak vezmeme kombináciu ( lambda = 3x ) a ( lambda = 1 ), dosadíme (1 ) do prvej rovnice za ( lambda ), čím dostaneme (1 = 3x ), takže (x = frac {1} {3} ). Pripojením tejto hodnoty k (x ) v rovnici obmedzenia a riešením pre (y ) získame (y = pm frac { sqrt {7}} {3} ), ktoré nám dá dve Lagrangeove body: ( left ( frac {1} {3}, - frac { sqrt {7}} {3} right) ) a ( left ( frac {1} {3}, frac { sqrt {7}} {3} vpravo) ).

Vyhodnotením funkcie (f ) v týchto Lagrangeových bodoch nájdeme: [ begin {align *} f (0, -1) & = 1 & f (0, 1) & = 1 f left ( - tfrac { sqrt {2}} {2}, 0 vpravo) & = frac {-4 ( sqrt {2}) ^ 3} {8} = - sqrt {2} & f doľava ( tfrac { sqrt {2}} {2}, 0 vpravo) & = frac {4 ( sqrt {2}) ^ 3} {8} = sqrt {2} f doľava ( tfrac {1} {3}, - tfrac { sqrt {7}} {3} vpravo) & = tfrac {25} {27} & f doľava ( tfrac {1} {3}, tfrac { sqrt {7}} {3} right) & = tfrac {25} {27} end {align *} ]

Porovnaním týchto hodnôt s tým, kde zodpovedajúce Lagrangeove body ležia na krivke obmedzenia, uzatvárame výsledky uvedené v odpovedi vyššie.

10) Objektívna funkcia: (f (x, y) = 2x ^ 2 + y ^ 2 ) Obmedzenie: (g (x, y) = x ^ 2 + y ^ 2 = 1 )

11) Objektívna funkcia: (f (x, y, z) = x + 3y − z ) Obmedzenie: (x ^ 2 + y ^ 2 + z ^ 2 = 4 )

12) Objektívna funkcia: (f (x, y, z) = x + y + z ) Obmedzenie: ( frac {1} {x} + frac {1} {y} + frac {1} {z} = 1 )

13) Objektívna funkcia: (f (x, y, z) = xyz ) Obmedzenie: (x ^ 2 + 2y ^ 2 + 3z ^ 2 = 6 )

14) Objektívna funkcia: (f (x, y, z) = x ^ 2 + y ^ 2 + z ^ 2 ) Obmedzenie: (x ^ 4 + y ^ 4 + z ^ 4 = 1 )

15) Objektívna funkcia: (f (x, y, z) = x ^ 2 + y ^ 2 + z ^ 2 ) Obmedzenie: (xyz = 4 )

V cvičeniach 16 - 21 použite metódu Lagrangeových multiplikátorov na nájdenie požadovaného extrému danej funkcie podliehajúcej danému obmedzeniu.

16) Maximalizujte (f (x, y) = sqrt {6 - x ^ 2 - y ^ 2} ) s výhradou obmedzenia, (x + y − 2 = 0 ).

17) Maximalizovať (f (x, y) = x ^ 2 - y ^ 2 ) s obmedzeniami, (g (x, y) = y − x ^ 2 = 0, quad x> 0, štvorkolka> 0 ).

18) Maximalizovať (U (x, y) = 8x ^ {4/5} y ^ {1/5} ) s výhradou obmedzenia, (4x + 2y = 12 ).

19) Minimalizujte (f (x, y, z) = x ^ 2 + y ^ 2 + z ^ 2 ) s výhradou obmedzenia, (x + y + z = 1 ).

20) Minimalizujte (f (x, y) = xy ) na elipse ( dfrac {x ^ 2} {a ^ 2} + dfrac {y ^ 2} {b ^ 2} = 1 ).

21) Maximalizujte (f (x, y, z) = 2x + 3y + 5z ) na sfére (x ^ 2 + y ^ 2 + z ^ 2 = 19 ).

V cvičeniach 22 - 23 použite metódu Lagrangeových multiplikátorov s dvoma obmedzeniami.

22) Optimalizujte (f (x, y, z) = yz + xy ) podľa obmedzení: (xy = 1, quad y ^ 2 + z ^ 2 = 1 ).

23) Minimalizovať (f (x, y, z) = x ^ 2 + y ^ 2 + z ^ 2 ), keď (x + y + z = 9 ) a (x + 2y + 3z = 20 ).

Na riešenie nasledujúcich aplikovaných problémov použite metódu Lagrangeových multiplikátorov.

24) Veľká nádoba v tvare obdĺžnikového pevného telesa musí mať objem 480 m3. Spodok kontajnera stojí 5 dolárov / m2 postaviť, zatiaľ čo horná a bočná strana stoja 3 USD / m2 zostrojiť. Použite Lagrangeove multiplikátory a nájdite rozmery kontajnera tejto veľkosti, ktoré majú minimálne náklady.

25) Obdĺžnikový box bez vrchnej časti (topless box) sa má vyrábať od 1212 ft2 z lepenky. Nájdite maximálny objem takejto škatule.

Riešenie:

26) Nájdite minimálnu vzdialenosť od paraboly (y = x ^ 2 ) po bod ((0,3) ).

27) Nájdite bod na priamke (y = 2x + 3 ), ktorý je najbližšie k bodu ((4,2) ).

Riešenie:

28) Päťuholník sa vytvorí umiestnením rovnoramenného trojuholníka na obdĺžnik, ako je to znázornené na diagrame. Ak je obvod päťuholníka 1010 palcov, nájdite dĺžky strán päťuholníka, ktoré maximalizujú plochu päťuholníka.

29) Nájdite minimálnu vzdialenosť od roviny (x + y + z = 1 ) k bodu ((2,1,1) ).

Riešenie:

30) Nájdite bod v rovine (4x + 3y + z = 2 ), ktorý je najbližšie k bodu ((1, −1,1) ).

31) [T] Investíciou (x ) jednotiek práce a (y ) jednotiek kapitálu môže výrobca hodiniek vyrobiť (P (x, y) = 50x ^ 0,4y ^ 0,6 ) hodinky. Nájdite maximálny počet hodiniek, ktoré je možné vyrobiť s rozpočtom 20 000 dolárov, ak náklady na prácu stoja 100 dolárov za jednotku a kapitálové náklady 200 dolárov za jednotku. Na naznačenie obrysového grafu funkcie použite grafik ako CalcPlot3D.

Riešenie:

32) Obdĺžniková pevná látka je obsiahnutá v štvorstene s vrcholmi ((1,0,0), , (0,1,0), , (0,0,1) ) a počiatkom. Základňa škatule má rozmery (x ) a (y ) a výška škatule je (z ). Ak je súčet (x ), (y ) a (z ) (1 ), nájdite rozmery, ktoré maximalizujú objem obdĺžnikového telesa.


2.11E: Cvičenie pre Lagrangeových multiplikátorov

V predchádzajúcej časti sme optimalizovali (t.j. našiel absolútne extrémy) funkcia v oblasti, ktorá obsahovala jeho hranicu. Nájsť potenciálne optimálne body vo vnútri regiónu nie je vo všeobecnosti zlé, stačilo len nájsť kritické body a zapojiť ich do funkcie. Ako sme však videli v príkladoch, hľadanie potenciálnych optimálnych bodov na hranici bol často dosť dlhý a chaotický proces.

V tejto časti sa pozrieme na ďalší spôsob optimalizácie funkcie podliehajúcej daným obmedzeniam. Obmedzením môže byť rovnica (rovnice), ktoré popisujú hranicu oblasti, aj keď v tejto časti sa nebudeme sústreďovať na tieto typy problémov, pretože táto metóda vyžaduje iba všeobecné obmedzenie a je jej úplne jedno, kde je dané obmedzenie prišiel z.

Poďme teda na vec. Chceme optimalizovať (t.j. nájsť minimálnu a maximálnu hodnotu) funkcie, (f doľava ( right) ), podlieha obmedzeniam (g left ( vpravo) = k ). Obmedzením môže byť opäť rovnica, ktorá popisuje hranicu oblasti, alebo nemusí byť. Tento proces je v skutočnosti pomerne jednoduchý, aj keď práca môže byť niekedy trochu ohromujúca.

Metóda Lagrangeových multiplikátorov

  1. Vyriešte nasledujúci systém rovníc. [začať nabla f dolava ( right) & = lambda , , nabla g left ( right) g left ( right) & = k end]
  2. Pripojte všetky riešenia, ( left ( right) ), od prvého kroku do (f doľava ( right) ) a identifikujte minimálnu a maximálnu hodnotu za predpokladu, že existujú, a ( nabla g ne vec <0> ) v danom bode.

Konštanta ( lambda ) sa nazýva Lagrangeov multiplikátor.

Všimnite si, že systém rovníc z metódy má v skutočnosti štyri rovnice, len sme systém napísali v jednoduchšej podobe. Aby sme to videli, vezmime si prvú rovnicu a vložme definíciu vektora gradientu, aby sme videli, čo dostaneme.

[ left langle <,,> right rangle = lambda left langle <,,> right rangle = left langle < lambda , lambda , lambda > pravý rangle ]

Aby boli tieto dva vektory rovnaké, musia byť rovnaké aj jednotlivé komponenty. Takže tu vlastne máme tri rovnice.

Tieto tri rovnice spolu s obmedzením (g left ( right) = c ), dajte štyri rovnice so štyrmi neznámymi (x ), (y ), (z ) a ( lambda ).

Všimnite si tiež, že ak máme iba funkcie dvoch premenných, nebudeme mať tretiu zložku gradientu a budeme mať iba tri rovnice v troch neznámych (x ), (y ) a ( lambda ).

Na záver si tiež musíme dať pozor na to, že v niektorých prípadoch minimá a maximá nebudú existovať, aj keď sa zdá, že metóda z nich vyplýva. Pri každom probléme sa musíme ubezpečiť, že budú existovať minimá a maximá skôr, ako problém začneme.

Vidieť fyzické zdôvodnenie vyššie uvedených vzorcov. Uvažujme minimálnu a maximálnu hodnotu (f left ( right) = 8 - 2 roky ) podlieha obmedzeniam ( + = 1 ). V praktických problémoch pre túto časť (presný problém č. 2) ukážeme minimálnu hodnotu (f left ( right) ) je -2, ktoré sa vyskytujú v ( left (<0,1> right) ) a maximálna hodnota (f left ( right) ) je 8,125, ktoré sa vyskytujú na ( left (<- frac << 3 sqrt 7 >> <8>, - frac <1> <8>> right) ) a ( vľavo (< frac << 3 sqrt 7 >> <8>, - frac <1> <8>> vpravo) ).

Tu je náčrt obmedzenia a (f doľava ( right) = k ) pre rôzne hodnoty (k ).

Najprv nezabudnite, že riešenia systému musia byť niekde na grafe obmedzenia, ( + = 1 ) v tomto prípade. Pretože hľadáme minimálnu / maximálnu hodnotu (f left ( right) ) to zase znamená, že umiestnenie minimálnej / maximálnej hodnoty (f left ( správny)), t.j. bod ( doľava ( right) ), musí sa vyskytnúť tam, kde graf (f left ( right) = k ) pretína graf obmedzenia, keď (k ) je minimálna alebo maximálna hodnota (f left ( správny)).

Teraz vidíme, že graf (f vľavo ( vpravo) = - 2 ), t.j. graf minimálnej hodnoty (f vľavo ( right) ), dotkne sa iba grafu obmedzenia na ( left (<0,1> right) ). V skutočnosti sú tieto dva grafy dotyčné.

Ak sú dva grafy dotyčné v danom bode, musia byť ich normálne vektory rovnobežné, t.j. dva normálne vektory musia byť navzájom skalárne násobky. Matematicky to znamená,

[ nabla f doľava ( right) = lambda , , nabla g left ( správny)]

pre nejaký skalár ( lambda ) a toto je presne prvá rovnica v systéme, ktorú musíme v metóde vyriešiť.

Upozorňujeme tiež, že ak (k ) je menšie ako minimálna hodnota (f left ( right) ) graf (f left ( right) = k ) nepretínajú graf obmedzenia, a preto nie je možné, aby funkcia prijala túto hodnotu (k ) v bode, ktorý obmedzenie uspokojí.

Rovnako, ak (k ) je väčšie ako minimálna hodnota (f vľavo ( right) ) graf (f left ( right) = k ) pretne graf obmedzenia, ale dva grafy nie sú dotyčnicové v priesečníku. To znamená, že metóda nenájde tieto priesečníky, keď budeme riešiť systém rovníc.

Ďalej uvedený graf zobrazuje inú množinu hodnôt (k ). V tomto prípade hodnoty (k ) zahŕňajú maximálnu hodnotu (f vľavo ( right) ) ako aj niekoľko hodnôt na oboch stranách maximálnej hodnoty.

Opäť vidíme, že graf (f vľavo ( right) = 8,125 ) sa dotkne iba grafu obmedzenia v dvoch bodoch. Je to dobrá vec, pretože vieme, že riešenie hovorí, že by malo dôjsť v dvoch bodoch. Všimnite si tiež, že v týchto bodoch je opäť graf (f vľavo ( right) = 8,125 ) a obmedzenie sú tangensové, takže rovnako ako pri minimálnych hodnotách musia byť v týchto bodoch aj bežné vektory rovnobežné.

Rovnako pre hodnotu (k ) väčšiu ako 8,125 je graf (f vľavo ( right) = k ) nepretína graf obmedzenia, a preto nebude možné pre (f left ( right) ) prevziať tie väčšie hodnoty v bodoch, ktoré sú obmedzené.

Taktiež pre hodnoty (k ) menšie ako 8,125 je graf (f vľavo ( right) = k ) pretína graf obmedzenia, ale nebude dotyčnicový v priesečníkoch, takže metóda opäť nevytvorí tieto priesečníky, keď budeme riešiť systém rovníc.

Takže s týmito grafmi sme videli, že minimálne / maximálne hodnoty (f left ( right) ) príde tam, kde bude graf (f left ( right) = k ) a graf obmedzenia sú dotyčnicové, takže ich normálne vektory sú rovnobežné. Aj preto, lebo bod musí nastať na samotnom obmedzení. Inými slovami, systém rovníc, ktoré musíme vyriešiť, aby sme určili minimálnu / maximálnu hodnotu (f left ( right) ) sú presne tie, ktoré sú uvedené vyššie, keď sme zaviedli metódu.

Všimnite si, že vyššie uvedené fyzické zdôvodnenie bolo urobené pre dvojrozmerný systém, ale rovnaké zdôvodnenie je možné vykonať aj vo vyšších dimenziách. Rozdiel je v tom, že vo vyšších dimenziách nebudeme pracovať s krivkami. Napríklad v troch rozmeroch by sme pracovali s povrchmi. Stále však budú platiť rovnaké myšlienky. V bodoch, ktoré poskytujú minimálnu a maximálnu hodnotu (hodnoty) plôch, by boli rovnobežné, a teda aj bežné vektory by boli rovnobežné.

Poďme si uviesť pár príkladov.

Predtým, ako začneme tento proces, všimnite si, že sme tiež videli spôsob, ako vyriešiť tento druh problému v kalkulu I, s výnimkou tých problémov, ktoré sme vyžadovali podmienku, ktorá spájala jednu zo strán skrinky s ostatnými stranami, aby sme mohli zísť dole na funkciu objemu a povrchovej plochy, ktorá zahŕňala iba dve premenné. Túto podmienku už pre tieto problémy nepotrebujeme.

Teraz poďme na riešenie problému. Najprv musíme určiť funkciu, ktorú ideme optimalizovať, ako aj obmedzenie. Nastavíme dĺžku poľa na (x ), šírku poľa na (y ) a výšku poľa na (z ). Upozorňujeme tiež, že pretože sa zaoberáme rozmermi škatule, dá sa predpokladať, že (x ), (y ) a (z ) sú všetky kladné veličiny.

Chceme nájsť najväčší objem a tak je funkcia, ktorú chceme optimalizovať, daná,

Ďalej vieme, že plocha poľa musí byť konštantná 64. Toto je teda obmedzenie. Plocha krabice je jednoducho súčet plôch každej zo strán, takže dané obmedzenie je dané,

[2xy + 2xz + 2yz = 64 hspace <0,5in> Rightarrow hspace <0,5in> xy + xz + yz = 32 ]

Všimnite si, že sme obmedzenie obmedzili na 2, aby sme rovnicu trochu zjednodušili. Dostaneme tiež funkciu (g left ( right) ) z toho.

Samotná funkcia, (f vľavo ( right) = xyz ) zjavne nebude mať ani minimá, ani maximá, pokiaľ na premenné neurobíme nejaké obmedzenia. Jediné skutočné obmedzenie, ktoré máme, je, že všetky premenné musia byť kladné. To samozrejme okamžite znamená, že funkcia má minimum, nulu, aj keď je to hlúpa hodnota, pretože to tiež znamená, že v podstate nemáme políčko. Znamená to však, že poznáme minimum (f vľavo ( right) ) existuje.

Pozrime sa teda, či (f vľavo ( right) ) bude mať maximum. Je zrejmé, že dúfam, (f vľavo ( right) ) nebude mať maximum, ak bude umožnené zvyšovanie všetkých premenných bez obmedzenia. To sa však nemôže stať z dôvodu obmedzenia,

Tu máme súčet troch kladných čísel (nezabudnite, že (x ), (y ) a (z ) sme kladné, pretože pracujeme s rámčekom) a súčet sa musí rovnať 32. Takže ak je jedna z premenných veľmi veľká, povedzme (x ), potom pretože každý z produktov musí byť menší ako 32, musia byť (y ) aj (z ) veľmi malé, aby sa zabezpečilo, že prvá dva členy sú menšie ako 32. Takže neexistuje žiadny spôsob, ako by sa všetky premenné mohli zväčšiť bez viazanosti, a preto by malo mať nejaký zmysel, že funkcia, (f left ( right) = xyz ), bude mať maximum.

Toto nie je presný dôkaz, že (f vľavo ( right) ) bude mať maximum, ale malo by to pomôcť vizualizovať to (f left ( right) ) by mala mať maximálnu hodnotu, pokiaľ je predmetom obmedzenia.

Tu sú štyri rovnice, ktoré musíme vyriešiť.

Existuje mnoho spôsobov, ako tento systém vyriešiť. Vyriešime to nasledujúcim spôsobom. Znásobme rovnicu ( eqref) pomocou (x ), rovnice ( eqref) pomocou (y ) a rovnice ( eqref) od (z ). To dáva,

Teraz si všimnite, že môžeme nastaviť rovnice ( eqref) a ( eqref) rovnaké. Toto dáva,

[začať lambda x vľavo ( right) & = lambda y left ( right) lambda left ( vpravo) - lambda vľavo ( right) & = 0 lambda left ( right) & = 0 hspace <0,5in> Rightarrow hspace <0,5in> lambda = 0 , , , , , , < mbox> , , , , , xz = yz koniec]

To dalo dve možnosti. Prvý znak ( lambda = 0 ) nie je možný, pretože ak by tomu tak bolo, rovnica ( eqref) zníži na

Pretože hovoríme o rozmeroch škatule, nie sú možné ani jedno z nich, takže môžeme zľavu ( lambda = 0 ) zľaviť. Zostáva tak druhá možnosť.

Pretože vieme, že (z ne 0 ) (opäť, keď hovoríme o rozmeroch škatule), môžeme (z ) zrušiť z oboch strán. To dáva,

Ďalej nastavíme rovnice ( eqref) a ( eqref) rovnaké. Toto dáva,

[začať lambda y vľavo ( right) & = lambda z left ( right) lambda left ( right) & = 0 lambda left ( right) & = 0 hspace <0,5in> Rightarrow hspace <0,5in> lambda = 0 , , , < mbox> , , , , yx = zx koniec]

Ako sme už diskutovali, vieme, že ( lambda = 0 ) nebude fungovať, a tak to odchádza,

Môžeme tiež povedať, že (x ne 0 ), pretože máme do činenia s rozmermi škatule, takže musíme mať,

Zapojenie rovníc ( eqref) a ( eqref) do rovnice ( eqref) dostaneme,

Vieme však, že (y ) musí byť kladné, pretože hovoríme o rozmeroch škatule. Jediné riešenie, ktoré tu dáva fyzický zmysel, je preto

Zdá sa teda, že máme kocku.

Tu by sme mali byť trochu opatrní. Pretože máme iba jedno riešenie, môžeme sa pokúsiť predpokladať, že práve tieto dimenzie poskytnú najväčší objem. Kedykoľvek dostaneme jediné riešenie, musíme si skutočne overiť, či je to maximum (alebo minimum, ak to hľadáme).

Toto je vlastne celkom jednoduché. Najprv si všimnime, že objem v našom riešení vyššie je,

Teraz vieme, že maximálne (f vľavo ( right) ) bude existovať („dokázané“ to skôr v riešení), a tak overiť, že toto je naozaj maximum, čo musíme urobiť, ak nájdeme inú množinu dimenzií, ktoré vyhovujú nášmu obmedzeniu, a skontrolujeme hlasitosť. Ak je objem tejto novej sady dimenzií menší ako objem vyššie, vieme, že naše riešenie dáva maximum.

Ak naopak nová sada rozmerov dáva väčší objem, máme problém. Máme iba jediné riešenie a vieme, že maximum existuje a metóda by toto maximum mala vygenerovať. Takže v tomto prípade je pravdepodobné, že niekde urobíme chybu a budeme sa musieť vrátiť a nájsť ju.

Poďme teda nájsť novú sadu rozmerov krabice. Jediná vec, ktorej sa musíme obávať, je, že uspokoja dané obmedzenie. Okrem toho neexistujú ďalšie obmedzenia týkajúce sa veľkosti rozmerov. Môžeme teda ľubovoľne zvoliť dve hodnoty a potom pomocou obmedzenia určiť tretiu hodnotu.

Vyberme (x = y = 1 ). Nie je žiadny dôvod pre tieto hodnoty, okrem toho, že je s nimi „ľahké“ pracovať. Ich zapojenie do obmedzenia dáva,

[1 + z + z = 32 hspace <0,25in> to hspace <0,25in> 2z = 31 hspace <0,25in> to hspace <0,25in> z = frac <<31>> < 2> ]

Toto je množina dimenzií, ktoré vyhovujú obmedzeniam, a objem tejto množiny dimenzií je,

Nové dimenzie teda dávajú menší objem, takže vyššie uvedené riešenie predstavuje v skutočnosti rozmery, ktoré poskytnú maximálny objem poľa, sú (x = y = z = , 3,266 )

Všimnite si, že v uvedenom príklade sme nikdy nenašli hodnoty pre ( lambda ). Je to pomerne štandardné pre tento druh problémov. Hodnota ( lambda ) nie je skutočne dôležitá na určenie, či je bod maximálny alebo minimálny, takže sa často nebudeme trápiť hľadaním jeho hodnoty. Príležitostne budeme potrebovať jeho hodnotu, aby sme pomohli vyriešiť systém, ale ani v tých prípadoch ho nebudeme používať pri hľadaní bodu.

Táto bude o niečo ľahšia ako predchádzajúca, pretože má iba dve premenné. Upozorňujeme tiež, že z obmedzenia je zrejmé, že oblasť možných riešení leží na disku s polomerom ( sqrt <136> ), ktorý je uzavretou a ohraničenou oblasťou, (- sqrt <136> le x, y le sqrt <13>>), a teda podľa vety o extrémnej hodnote vieme, že musí existovať minimálna a maximálna hodnota.

Tu je systém, ktorý musíme vyriešiť.

[začať5 & ​​= 2 lambda x - 3 & = 2 lambda y + & = 136 koniec]

Všimnite si, že rovnako ako v poslednom príklade nemôžeme mať ( lambda = 0 ), pretože to by nespĺňalo prvé dve rovnice. Pretože vieme, že ( lambda ne 0 ), môžeme vyriešiť prvé dve rovnice pre (x ) a (y ). To dáva,

Ich zapojenie do obmedzenia dáva,

Môžeme to vyriešiť pre ( lambda ).

Teraz, keď vieme ( lambda ), môžeme nájsť body, ktoré budú potenciálnymi maximami a / alebo minimami.

a ak ( lambda = frac <1> <4> ) dostaneme,

Aby sme zistili, či máme maximá alebo minimá, stačí ich zapojiť do funkcie. Pripomeňme tiež z diskusie na začiatku tohto riešenia, že vieme, že to budú minimá a maximá, pretože veta o extrémnej hodnote nám hovorí, že pre tento problém budú existovať minimá a maximá.

Tu sú minimálne a maximálne hodnoty funkcie.

V prvých dvoch príkladoch sme vylúčili ( lambda = 0 ) buď z fyzikálnych dôvodov, alebo preto, že by sa tým nevyriešila jedna alebo viac rovníc. Nečakajte vždy, že sa tak stane. Niekedy budeme schopní automaticky vylúčiť hodnotu ( lambda ) a niekedy nebudeme.

Pozrime sa na ďalší príklad.

Prvá poznámka, že naše obmedzenie je súčtom troch kladných alebo nulových čísel a musí byť 1. Preto je zrejmé, že naše riešenie bude spadať do rozsahu (0 le x, y, z le 1 ) a tak riešenie musí ležať v uzavretej a ohraničenej oblasti a tak podľa vety o extrémnej hodnote vieme, že musí existovať minimálna a maximálna hodnota.

Tu je systém rovníc, ktorý musíme vyriešiť.

Začnime tento proces riešenia tým, že si všimneme, že keďže všetky prvé tri rovnice majú ( lambda ), sú všetky rovnaké. Začnime teda nastavením rovníc ( eqref) a ( eqref) rovnaké.

Máme tu teda dve možnosti. Začnime s predpokladom, že (z = 0 ). V tomto prípade vidíme buď z rovnice ( eqref) alebo ( eqref) že potom musíme mať ( lambda = 0 ). Z rovnice ( ekv) vidíme, že to znamená (xy = 0 ). To zase znamená, že buď ​​(x = 0 ), alebo (y = 0 ).

Máme tu teda dva možné prípady, ktoré budeme riešiť. V obidvoch prípadoch musia byť dve z premenných nula. Keď to vieme, môžeme sa zapojiť do obmedzenia, rovnice ( eqref), aby ste našli zvyšnú hodnotu.

[začaťz = 0, , , x = 0 &: & Rightarrow hspace <0,25in> y = 1 z = 0, , , y = 0 &: & Rightarrow hspace <0,25in> x = 1 koniec]

Takže máme dve možné riešenia ( left (<0,1,0> right) ) a ( left (<1,0,0> right) ).

Teraz sa vráťme späť a pozrime sa na ďalšiu možnosť (y = x ). Máme tu tiež dva možné prípady, na ktoré sa pozrieme.

Tento prvý prípad je (x = y = 0 ). V tomto prípade z obmedzenia vidíme, že musíme mať (z = 1 ), a tak máme teraz tretie riešenie ( left (<0,0,1> right) ).

Druhý prípad je (x = y ne 0 ). Nastavme rovnice ( eqref) a ( eqref) rovnaké.

Teraz sme už predpokladali, že (x ne 0 ), takže jediná možnosť je (z = y ). To však tiež znamená, že

Použitie tohto obmedzenia dáva,

Takže ďalšie riešenie je ( left (<3>,frac<1><3>,frac<1> <3>> right) ).

Dostali sme štyri riešenia nastavením rovnosti prvých dvoch rovníc.

Aby sme tento problém úplne dokončili, mali by sme pravdepodobne nastaviť rovnice ( eqref) a ( eqref) rovnaké ako aj nastavenie rovníc ( eqref) a ( eqref) rovnaké, aby sme videli, čo dostaneme. Toto dáva,

Oba sú veľmi podobné prvej situácii, na ktorú sme sa pozreli, a necháme na vás, aby sme ukázali, že v každom z týchto prípadov prichádzame späť k štyrom riešeniam, ktoré sme už našli.

Máme teda štyri riešenia, ktoré musíme skontrolovať vo funkcii, aby sme zistili, či máme minimá alebo maximá.

V tomto prípade sa teda maximum vyskytuje iba raz, kým minimum trikrát.

Upozorňujeme tiež, že sme nikdy skutočne nepoužili predpoklad, že (x, y, z ge 0 ) v skutočnom riešení problému. Použili sme to na zabezpečenie toho, aby sme mali uzavretú a ohraničenú oblasť, ktorá nám zaručí, že budeme mať absolútne extrémy. Aby sme zistili, prečo je to dôležité, pozrime sa, čo by sa mohlo stať bez tohto predpokladu. Bez tohto predpokladu by nebolo príliš ťažké nájsť body, ktoré poskytujú väčšie aj menšie hodnoty funkcií. Napríklad.

Na týchto príkladoch môžete jasne vidieť, že nie je príliš ťažké nájsť body, ktoré budú dávať väčšie a menšie funkčné hodnoty. Všetky tieto príklady však vyžadovali záporné hodnoty (x ), (y ) a / alebo (z ), aby sme sa ubezpečili, že dané obmedzenie spĺňame. Ak ich vylúčime, budeme vedieť, že podľa vety o extrémnej hodnote máme minimálne a maximálne hodnoty.

Predtým, ako budeme pokračovať, sa musíme venovať rýchlemu problému, ktorý posledný príklad ilustruje o metóde Lagrangeových multiplikátorov. Našli sme absolútne minimum a maximum funkcie. Čo sme však nenašli, sú všetky lokality pre absolútne minimum. Napríklad za predpokladu (x, y, z ge 0 ) zvážte nasledujúce množiny bodov.

Každý bod v tejto množine bodov uspokojí obmedzenie problému a funkcia sa v každom prípade vyhodnotí na nulu, a teda dá aj absolútne minimum.

Takže, čo sa deje? Pripomeňme si z predchádzajúcej časti, že sme museli skontrolovať kritické body aj hranice, aby sme sa uistili, že máme absolútne extrémy. To isté platilo aj v kalkulu I. Museli sme skontrolovať kritické aj koncové body intervalu, aby sme sa uistili, že máme absolútne extrémy.

Ukázalo sa, že tu musíme skutočne urobiť to isté, ak chceme vedieť, že sme našli všetky polohy absolútnych extrémov. Metóda Lagrangeových multiplikátorov nájde absolútne extrémy, len nemusí nájsť všetky ich umiestnenia, pretože metóda nezohľadňuje koncové body rozsahov premenných (všimnite si, že do niektorých z týchto bodov môžeme mať šťastie, ale môžeme ' to nezaručujem).

Po absolvovaní Lagrangeovej multiplikátorovej metódy by sme sa mali spýtať, čo sa stane v koncových bodoch našich variabilných rozsahov. Napríklad to znamená pozrieť sa na to, čo sa stane, keď (x = 0 ), (y = 0 ), (z = 0 ), (x = 1 ), (y = 1 ), a (z = 1 ). V prvých troch prípadoch dostaneme vyššie uvedené body, ktoré tiež dajú absolútne minimum. Pre posledné tri prípady vidíme, že ak je jedna z premenných 1, ďalšie dve musia byť nulové (aby vyhovovali obmedzeniam) a tie sa v príklade skutočne našli. Niekedy sa to stane a niekedy nie.

V prípade tohto príkladu dali koncové body každého z premenných rozsahov absolútne extrémy, ale nie je dôvod očakávať, že k tomu dôjde zakaždým. Napríklad v príklade 2 vyššie napríklad koncové body rozsahov premenných nedávajú absolútne extrémy (overíme vás to).

Morálka je taká, že ak chceme vedieť, že máme každé miesto absolútnych extrémov pre konkrétny problém, mali by sme skontrolovať aj koncové body akýchkoľvek variabilných rozsahov, ktoré by sme mohli mať. Ak nás zaujíma iba hodnota absolútnych extrémov, nie je dôvod to robiť.

Dobre, je čas prejsť na trochu inú tému. Do tohto bodu sme sa pozreli iba na obmedzenia, ktoré boli rovnicami. Môžeme mať aj obmedzenia, ktoré sú nerovnosťou. Proces pre tieto typy problémov je takmer totožný s tým, čo sme robili v tejto časti až do tohto bodu. Hlavný rozdiel medzi týmito dvoma typmi problémov je v tom, že tiež budeme musieť nájsť všetky kritické body, ktoré uspokojujú nerovnosť obmedzenia, a skontrolovať ich vo funkcii, keď kontrolujeme hodnoty, ktoré sme našli pomocou Lagrangeových multiplikátorov.

Ukážme si príklad, ako fungujú tieto druhy problémov.

Upozorňujeme, že obmedzením je nerovnosť disku. Pretože sa jedná o uzavretú a ohraničenú oblasť, veta o extrémnej hodnote nám hovorí, že musí existovať minimálna a maximálna hodnota.

Prvým krokom je nájsť všetky kritické body, ktoré sa na disku nachádzajú (t.j. obmedzenia). Pre tento problém je to dosť ľahké urobiť. Tu sú dva čiastkové deriváty prvého rádu.

[začať & = 8x & & Rightarrow hspace <0,25in> , , , 8x = 0 hspace <0,25in> Rightarrow hspace <0,25in> , , , , , , x = 0 & = 20 rokov & & Rightarrow hspace <0,25in> 20y = 0 hspace <0,25in> Rightarrow hspace <0,25in> , , , , , , y = 0 koniec]

Jediným kritickým bodom je teda ( ľavý (<0,0> pravý) ), ktorý spĺňa nerovnosť.

V tomto bode pokračujeme Lagrangeovými multiplikátormi a s obmedzeniami zaobchádzame ako s rovnosťou namiesto s nerovnosťou. We only need to deal with the inequality when finding the critical points.

So, here is the system of equations that we need to solve.

[egin8x & = 2lambda x 20y & = 2lambda y + & = 4end]

From the first equation we get,

If we have (x = 0) then the constraint gives us (y = pm ,2).

If we have (lambda = 4) the second equation gives us,

[20y = 8yhspace <0.25in>Rightarrow hspace<0.25in>,,,y = 0]

The constraint then tells us that (x = pm ,2).

If we’d performed a similar analysis on the second equation we would arrive at the same points.

So, Lagrange Multipliers gives us four points to check :(left( <0,2> ight)), (left( <0, - 2> ight)), (left( <2,0> ight)), and (left( < - 2,0> ight)).

To find the maximum and minimum we need to simply plug these four points along with the critical point in the function.

In this case, the minimum was interior to the disk and the maximum was on the boundary of the disk.

The final topic that we need to discuss in this section is what to do if we have more than one constraint. We will look only at two constraints, but we can naturally extend the work here to more than two constraints.

We want to optimize (fleft( ight)) subject to the constraints (gleft( ight) = c) and (hleft( ight) = k). The system that we need to solve in this case is,

[egin abla fleft( ight) & = lambda abla gleft( ight) + mu abla hleft( ight) gleft( ight) & = c hleft( ight) & = kend]

So, in this case we get two Lagrange Multipliers. Also, note that the first equation really is three equations as we saw in the previous examples. Let’s see an example of this kind of optimization problem.

Verifying that we will have a minimum and maximum value here is a little trickier. Clearly, because of the second constraint we’ve got to have ( - 1 le x,y le 1). With this in mind there must also be a set of limits on (z) in order to make sure that the first constraint is met. If one really wanted to determine that range you could find the minimum and maximum values of (2x - y) subject to ( + = 1) and you could then use this to determine the minimum and maximum values of (z). We won’t do that here. The point is only to acknowledge that once again the possible solutions must lie in a closed and bounded region and so minimum and maximum values must exist by the Extreme Value Theorem.

Here is the system of equations that we need to solve.

First, let’s notice that from equation (eqref) we get (lambda = 2). Plugging this into equation (eqref) and equation (eqref) and solving for (x) and (y) respectively gives,

[egin0 & = 4 + 2mu x & hspace <0.1in>& Rightarrow hspace<0.5in>x = - frac<2> 4 & = - 2 + 2mu y & hspace <0.1in>& Rightarrow hspace<0.5in>y = frac<3>end]

Now, plug these into equation (eqref).

So, we have two cases to look at here. First, let’s see what we get when (mu = sqrt <13>). In this case we know that,

Plugging these into equation (eqref) gives,

Let’s now see what we get if we take (mu = - sqrt <13>). Here we have,

Plugging these into equation (eqref) gives,

and there’s a second solution.

Now all that we need to is check the two solutions in the function to see which is the maximum and which is the minimum.


2.11E: Exercises for Lagrange Multipliers

Using Lagrange Multipliers

In Exercises 3–10, use Lagrange Multipliers to find the indicated extrema, assuming that

Using Lagrange Multipliers

In Exercises 3–10, use Lagrange Multipliers to find the indicated extrema, assuming that

Using Lagrange Multipliers

In Exercises 3–10, use Lagrange Multipliers to find the indicated extrema, assuming that


2.11E: Exercises for Lagrange Multipliers

1. Find the maximum and minimum values of (fleft( ight) = 81 + ) subject to the constraint (4 + = 9).

Show All Steps Hide All Steps

Before proceeding with the problem let’s note because our constraint is the sum of two terms that are squared (and hence positive) the largest possible range of (x) is ( - frac<3> <2>le x le frac<3><2>) (the largest values would occur if (y = 0)). Likewise, the largest possible range of (y) is ( - 3 le y le 3) (with the largest values occurring if (x = 0)).

Note that, at this point, we don’t know if (x) and/or (y) will actually be the largest possible value. At this point we are simply acknowledging what they are. What this allows us to say is that whatever our answers will be they must occur in these bounded ranges and hence by the Extreme Value Theorem we know that absolute extrema will occur for this problem.

This step is an important (and often overlooked) step in these problems. It always helps to know that absolute extrema exist prior to actually trying to find them!

The first actual step in the solution process is then to write down the system of equations we’ll need to solve for this problem.

[egin162x & = 8xlambda 2y & = 2ylambda 4 + & = 9end] Show Step 3

For most of these systems there are a multitude of solution methods that we can use to find a solution. Some may be harder than other, but unfortunately, there will often be no way of knowing which will be “easy” and which will be “hard” until you start the solution process.

Do not be afraid of these systems. They are probably unlike anything you’ve ever really been asked to solve up to this point. Most of the systems can be solved using techniques that you already know and aren’t really as “bad” as they may appear at first glance. Some do require some additional techniques and can be quite messy but for the most part still involve techniques that you do know how to use, you just may not have ever seen them done in the context of solving systems of equations.

In this case, simply because the numbers are a little smaller, let’s start with the second equation. A little rewrite of the equation gives us the following,

Be careful here to not just divide both sides by (y) to “simplify” the equation. Remember that you can’t divide by anything unless you know for a fact that it won’t ever be zero. In this case we can see that (y) clearly can be zero and if you divide it out to start the solution process you will miss that solution. This is often one of the biggest mistakes that students make when working these kinds of problems.

We now have two possibilities from Step 3. Either (y = 0) or (lambda = 1). We’ll need to go through both of these possibilities and see what we get.

Let’s start by assuming that (y = 0). In this case we can go directly to the constraint to get,

Therefore, from this part we get two points that are potential absolute extrema,

Next, let’s assume that (lambda = 1). In this case, we can plug this into the first equation to get,

[162x = 8xhspace <0.25in> o hspace<0.25in>154x = 0hspace <0.25in> o hspace<0.25in>x = 0]

So, under this assumption we must have (x = 0). We can now plug this into the constraint to get,

So, this part gives us two more points that are potential absolute extrema,

[left( <0, - 3> ight)hspace<0.5in>left( <0,3> ight)] Show Step 6

In total, it looks like we have four points that can potentially be absolute extrema. So, to determine the absolute extrema all we need to do is evaluate the function at each of these points. Here are those function evaluations.

The absolute maximum is then (frac<<729>> <4>= 182.25) which occurs at (left( < - frac<3><2>,0> ight)) and (left( <2>,0> ight)). The absolute minimum is 9 which occurs at (left( <0, - 3> ight)) and (left( <0,3> ight)). Do not get excited about the absolute extrema occurring at multiple points. That will happen on occasion with these problems.


2.11E: Exercises for Lagrange Multipliers

Using Lagrange Multipliers

In Exercises 11–14, use Lagrange Multipliers to find the indicated extrema, assuming that

Using Lagrange Multipliers

In Exercises 11–14, use Lagrange multipliers to find the indicated extrema, assuming that

Using Lagrange Multipliers

In Exercises 11–14, use Lagrange multipliers to find the indicated extrema, assuming that


Lagrange’s Mean Value Theorem

Lagrange’s mean value theorem (MVT) states that if a function (fleft( x ight)) is continuous on a closed interval (left[ ight]) and differentiable on the open interval (left( ight),) then there is at least one point (x = c) on this interval, such that

[fleft( b ight) – fleft( a ight) = f’left( c ight)left( ight).]

This theorem (also known as First Mean Value Theorem ) allows to express the increment of a function on an interval through the value of the derivative at an intermediate point of the segment.

Dôkaz.

Consider the auxiliary function

[Fleft( x ight) = fleft( x ight) + lambda x.]

We choose a number (lambda) such that the condition (Fleft( a ight) = Fleft( b ight)) is satisfied. Potom

The function (Fleft( x ight)) is continuous on the closed interval (left[ ight],) differentiable on the open interval (left( ight)) and takes equal values at the endpoints of the interval. Therefore, it satisfies all the conditions of Rolle’s theorem. Then there is a point (c) in the interval (left( ight)) such that

[fleft( b ight) – fleft( a ight) = f’left( c ight)left( ight).]

Fig.1 Joseph-Louis Lagrange (1736-1813)

Geometric interpretation

Lagrange’s mean value theorem has a simple geometrical meaning . The chord passing through the points of the graph corresponding to the ends of the segment (a) and (b) has the slope equal to

Then there is a point (x = c) inside the interval (left[ ight],) where the tangent to the graph is parallel to the chord (Figure (2)).

Physical interpretation

The mean value theorem has also a clear physical interpretation . If we assume that (fleft( t ight)) represents the position of a body moving along a line, depending on the time (t,) then the ratio of

is the average velocity of the body in the period of time (b – a.) Since (f’left( t ight)) is the instantaneous velocity, this theorem means that there exists a moment of time (c,) in which the instantaneous speed is equal to the average speed.

Lagrange’s mean value theorem has many applications in mathematical analysis, computational mathematics and other fields. Let us further note two remarkable corollaries .

Corollary (1)

In a particular case when the values of the function (fleft( x ight)) at the endpoints of the segment (left[ ight]) are equal, i.e. (fleft( a ight) = fleft( b ight),) the mean value theorem implies that there is a point (c in left( ight)) such that

that is, we get Rolle’s theorem, which can be considered as a special case of Lagrange’s mean value theorem.

Corollary (2)

If the derivative (f’left( x ight)) is zero at all points of the interval (left[ ight],) then the function (fleft( x ight)) is constant on this interval. Indeed, for any two points () and () in the interval (left[ ight],) there exists a point (c in left( ight)) such that


Two useful next steps are to add support for resting contact so the bodies can stack, and to add hard constraints so you can build more interesting compound jointed mechanisms, like ragdolls and cars and whatnot. Resting contact is in some ways a superset of hard constraints, and it's certainly more difficult to do right, so a good next step in learning is to implement constraints.

There are a lot of ways to implement hard constraints, and they vary in performance, stability, accuracy, and difficulty of programming. They each have pros and cons. Some of the more popular methods include:

  • Augmented Coordinates / Lagrange Multipliers with explicit integration
    • The topic of this article.
    • Often Featherstone's and Balafoutis and Patel's algorithms are used for this, also see my Physics References.
    • Dave Wu is the master of this, and I've implemented several variations based on his research.
    • Thomas Jakobsen's excellent GDC presentation discusses this method.

    I've implemented all of these and a few others to boot (see Five Physics Simulators for Articulated Bodies for discussion of the first three as well), and I hope to eventually have articles about all of them, and discuss the tradeoffs and pros and cons.

    Lagrange Multipliers

    The first technique I implemented when I was investigating constrained dynamics were "Augmented Coordinates with Lagrange Multipliers". It sounds complicated, but at its heart it simply means you calculate all the known external forces on your objects from things like gravity, springs, explosions, and whatnot, and then you compute the forces necessary to add into those external forces to keep the constraints satisfied. So, if you have an object constrained to slide on the floor, and you're not pulling on it, the constraint forces computed might be 0, or they might be just enough to counteract gravity if you're simulating it. If you pull up, the constraints pull down to cancel out your pull. If you slide the block sideways, the constraint forces do not try to stop you, and the block slides, but can't move up and down.

    In that example, we were probably using a 3DOF constraint, one translational DOF to prevent the block from leaving the floor, and 2 rotational DOFs to prevent the block from rotating except about the normal to the floor (so it doesn't rotate into the floor). One great feature of Lagrange Multiplier constraints is that they explicitly subtract off the DOFs one at a time, and you can control them in a very modular way. So, you can easily have the same code handle constraining any combination of the 6 DOFs of a rigid body. Once you get your simulator working (or if you play with my sample code below) you can see this modularity in action.

    The Math

    The math for Lagrange Multiplier constraints is very clean and elegant, and it can be expressed at a high level very parsimoniously. Here is the full general derivation of the technique for arbitrary DOF constraints. Obviously, the lecture and articles below go through this math at a much lower level and with more details, and they don't actually lift up to this level of generality due to space and time constraints, but all the detailed nitty gritty math in the lecture and articles is subsumed by this math in its most general form. It is worth noting the sample code actually does directly implement this general math, however.

    Writing Constraint Equations

    After you've got the basic constraint structure in place, it all comes down to writing the constraint equations. The articles, lecture, and sample code all just focus on a 3DOF point constraint, but I'll eventually write up some stuff about implementing other kinds of constraints. Writing constraint equations is actually a deeper exercise than it appears initially, there is some really important math to explore in writing the signed distance functions that make good constraint equations.

    todo: lots more work to do on this page

    Lectures and Articles

    I decided to extend my rigid body articles to discuss simulating a ponytail with hard constraints back in 1999 at the Game Developers Conference Roadshow in Seattle, then I wrote a two-part article about it for Game Developer Magazine and gave the lecture at the 2000 GDC.


    2.11E: Exercises for Lagrange Multipliers

    Convex Analysis and Optimization

    This book focuses on the theory of convex sets and functions, and its connections with a number of topics that span a broad range from continuous to discrete optimization. These topics include Lagrange multiplier theory, Lagrangian and conjugate/Fenchel duality, minimax theory, and nondifferentiable optimization.

    The book evolved from a set of lecture notes for a graduate course at M.I.T. It is widely recognized that, aside from being an eminently useful subject in engineering, operations research, and economics, convexity is an excellent vehicle for assimilating some of the basic concepts of real analysis within an intuitive geometrical setting. Unfortunately, the subject's coverage in academic curricula is scant and incidental. We believe that at least part of the reason is the shortage of textbooks that are suitable for classroom instruction, particularly for nonmathematics majors. We have therefore tried to make convex analysis accessible to a broader audience by emphasizing its geometrical character, while maintaining mathematical rigor. We have included as many insightful illustrations as possible, and we have used geometric visualization as a principal tool for maintaining the students' interest in mathematical proofs.

    Our treatment of convexity theory is quite comprehensive, with all major aspects of the subject receiving substantial treatment. The mathematical prerequisites are a course in linear algebra and a course in real analysis in finite dimensional spaces (which is the exclusive setting of the book). A summary of this material, without proofs, is provided in Section 1.1. The coverage of the theory has been significantly extended in the exercises, which represent a major component of the book. Detailed solutions of all the exercises (nearly 200 pages) are internet-posted in the book's www page

    Some of the exercises may be attempted by the reader without looking at the solutions, while others are challenging but may be solved by the advanced reader with the assistance of hints. Still other exercises represent substantial theoretical results, and in some cases include new and unpublished research. Readers and instructors should decide for themselves how to make best use of the internet-posted solutions.

    An important part of our approach has been to maintain a close link between the theoretical treatment of convexity and its application to optimization. For example, in Chapter 2, after the development of some of the basic facts about convexity, we discuss some of their applications to optimization and saddle point theory in Chapter 3, after the discussion of polyhedral convexity, we discuss its application in linear and integer programming and in Chapter 4, after the discussion of subgradients, we discuss their use in optimality conditions. We follow this style in the remaining chapters, although having developed in Chapters 1-4 most of the needed convexity theory, the discussion in the subsequent chapters is more heavily weighted towards optimization.

    The chart of the opposite page illustrates the main topics covered in the book, and their interrelations. At the top level, we have the most basic concepts of convexity theory, which are covered in Chapter 1. At the middle level, we have fundamental topics of optimization, such as existence and characterization of solutions, and minimax theory, together with some supporting convexity concepts such as hyperplane separation, polyhedral sets, and subdifferentiability (Chapters 2-4). At the lowest level, we have the core issues of convex optimization: Lagrange multipliers, Lagrange and Fenchel duality, and numerical dual optimization (Chapters 5-8).

    An instructor who wishes to teach a course from the book has a choice between several different plans. One possibility is to cover in detail just the first four chapters, perhaps augmented with some selected sections from the remainder of the book, such as the first section of Chapter 7, which deals with conjugate convex functions. The idea here is to concentrate on convex analysis and illustrate its application to minimax theory through the minimax theorems of Chapters 2 and 3, and to constrained optimization theory through the Nonlinear Farkas' Lemma of Chapter 3 and the optimality conditions of Chapter 4. An alternative plan is to cover Chapters 1-4 in less detail in order to allow some time for Lagrange multiplier theory and computational methods. Other plans may also be devised, possibly including some applications or some additional theoretical topics of the instructor's choice.

    While the subject of the book is classical, the treatment of several of its important topics is new and in some cases relies on new research. In particular, our new lines of analysis include:

    <(a)>A unified development of minimax theory and constrained optimization duality as special cases of the duality between two simple geometrical problems: the min common point problem and the max crossing point problem. Here, by minimax theory, we mean the analysis relating to the minimax equality

    and the attainment of the "inf" and the "sup." By constrained optimization theory, we mean the analysis of problems such as

    subject to xin X, g_j(x) Min Common/Max Crossing Duality

    In this book, duality theory is captured in two easily visualized problems: the min common point problem and the max crossing point problem, introduced in Chapter 2. Fundamentally, these problems revolve around the existence of nonvertical supporting hyperplanes to convex sets that are unbounded from above along the vertical axis. When properly specialized, this turns out to be the critical issue in constrained optimization duality and saddle point/minimax theory, under standard convexity and/or concavity assumptions.

    The salient feature of the min common/max crossing framework is its simple geometry, in the context of which the fundamental constraint qualifications needed for strong duality theorems are visually apparent, and admit straightforward proofs. This allows the development of duality theory in a unified way: first within the min common/max crossing framework in Chapters 2 and 3, and then by specialization, to saddle point and minimax theory in Chapters 2 and 3, and to optimization duality in Chapter 6. All of the major duality theorems discussed in this book are derived in this way, including the principal Lagrange multiplier and Fenchel duality theorems for convex programming, and the von Neuman Theorem for zero sum games.

    From an instructional point of view, it is particularly desirable to unify constrained optimization duality and saddle point/minimax theory (under convexity/concavity assumptions). Their connection is well known, but it is hard to understand beyond a superficial level, because there is not enough overlap between the two theories to develop one in terms of the other. In our approach, rather than trying to build a closer connection between constrained optimization duality and saddle point/minimax theory, we show how they both stem from a common geometrical root: the min common/max crossing duality.

    We note that the constructions involved in the min common and max crossing problems arise in the theories of subgradients, conjugate convex functions, and duality. As such they are implicit in several earlier analyses in fact they have been employed for visualization purposes in the first author's nonlinear programming textbook [Ber99]. However, the two problems have not been used as a unifying theoretical framework for constrained optimization duality, saddle point theory, or other contexts, except implicitly through the theory of conjugate convex functions, and the complicated and specialized machinery of conjugate saddle functions. Pedagogically, it appears desirable to postpone the introduction of conjugacy theory until it is needed for the limited purposes of Fenchel duality (Chapter 7), and to bypass altogether conjugate saddle function theory, which is what we have done.

    Existence of Solutions and Strong Duality

    We show that under convexity assumptions, several fundamental issues in optimization are intimately related. In particular, we give a unified analysis of conditions for optimal solutions to exist, for the minimax equality to hold, and for the absence of a duality gap in constrained optimization.

    To provide a sense of the main idea, we note that given a constrained optimization problem, lower semicontinuity of the cost function and compactness of the constraint set guarantee the existence of an optimal solution (the Weierstrass Theorem). On the other hand, the same conditions plus convexity of the cost and constraint functions guarantee not only the existence of an optimal solution, but also the absence of a duality gap. This is not a coincidence, because as it turns out, the conditions for both cases critically rely on the same fundamental properties of compact sets, namely that the intersection of a nested family of nonempty compact sets is nonempty and compact, and that the projections of compact sets on any subspace are compact.

    In our analysis, we extend this line of reasoning under a variety of assumptions relating to convexity, directions of recession, polyhedral sets, and special types of sets specified by quadratic and other types of inequalities. The assumptions are used to establish results asserting that the intersection of a nested family of closed convex sets is nonempty, and that the function $f(x)=inf_zF(x,z)$, obtained by partial minimization of a convex function $F$, is lower semicontinuous. These results are translated in turn to a broad variety of conditions that guarantee the existence of optimal solutions, the minimax equality, and the absence of a duality gap.

    Pseudonormality and Lagrange Multipliers

    In Chapter 5, we discuss Lagrange multiplier theory in the context of optimization of a smooth cost function, subject to smooth equality and inequality constraints, as well as an additional set constraint. Our treatment of Lagrange multipliers is new, and aims to generalize, unify, and streamline the theory of constraint qualifications.

    The starting point for our development is an enhanced set of necessary conditions of the Fritz John type, that are sharper than the classical Karush-Kuhn-Tucker conditions (they include extra conditions, which may narrow down the field of candidate local minima). They are also more general in that they apply when there is an abstract (possibly nonconvex) set constraint, in addition to the equality and inequality constraints. To achieve this level of generality, we bring to bear notions of nonsmooth analysis, and we find that the notion of regularity of the abstract constraint set provides the critical distinction between problems that do and do not admit a satisfactory theory.

    Fundamentally, Lagrange multiplier theory should aim to identify the essential constraint structure that guarantees the existence of Lagrange multipliers. For smooth problems with equality and inequality constraints, but no abstract set constraint, this essential structure is captured by the classical notion of quasiregularity (the tangent cone at a given feasible point is equal to the cone of first order feasible variations). However, in the presence of an additional set constraint, the notion of quasiregularity breaks down as a viable unification vehicle. Our development introduces the notion of pseudonormality as a substitute for quasiregularity for the case of an abstract set constraint. Pseudonormality unifies and expands the major constraint qualifications, and simplifies the proofs of Lagrange multiplier theorems. In the case of equality constraints only, pseudonormality is implied by either one of two alternative constraint qualifications: the linear independendence of the constraint gradients and the linearity of the constraint functions. In fact, in this case, pseudonormality is not much different than the union of these two constraint qualifications. However, pseudonormality is a meaningful unifying property even in the case of an additional set constraint, where the classical proof arguments based on quasiregularity fail. Pseudonormality also provides the connecting link between constraint qualifications and the theory of exact penalty functions.

    An interesting byproduct of our analysis is a taxonomy of different types of Lagrange multipliers for problems with nonunique Lagrange multipliers. Under some convexity assumptions, we show that if there exists at least one Lagrange multiplier vector, there exists at least one of a special type, called informative, which has nice sensitivity properties. The nonzero components of such a multiplier vector identify the constraints that need to be violated in order to improve the optimal cost function value. Furthermore, a particular informative Lagrange multiplier vector characterizes the direction of steepest rate of improvement of the cost function for a given level of the norm of the constraint violation. Along that direction, the equality and inequality constraints are violated consistently with the signs of the corresponding multipliers.

    The theory of enhanced Fritz John conditions and pseudonormality are extended in Chapter 6 to the case of a convex programming problem, without assuming the existence of an optimal solution or the absence of a duality gap. They form the basis for a new line of analysis for asserting the existence of informative multipliers under the standard constraint qualifications.

    Incremental Subgradient Methods

    In Chapter 8, we discuss one of the most important uses of duality: the numerical solution of dual problems, often in the context of discrete optimization and the method of branch-and-bound. These dual problems are often nondifferentiable and have special structure. Subgradient methods have been among the most popular for the solution of these problems, but they often suffer from slow convergence.

    We introduce incremental subgradient methods, which aim to accelerate the convergence by exploiting the additive structure that a dual problem often inherits from properties of its primal problem, such as separability. In particular, for the common case where the dual function is the sum of a large number of component functions, incremental methods consist of a sequence of incremental steps, each involving a single component of the dual function, rather than the sum of all components.

    Our analysis aims to identify effective variants of incremental methods, and to quantify their advantages over the standard subgradient methods. An important question is the selection of the order in which the components are selected for iteration. A particularly interesting variant uses randomization of the order to resolve a worst-case complexity bottleneck associated with the natural deterministic order. According to both analysis and experiment, this randomized variant performs substantially better than the standard subgradient methods for large scale problems that typically arise in the context of duality. The randomized variant is also particularly well-suited for parallel, possibly asynchronous, implementation, and is the only available method, to our knowledge, that can be used efficiently within this context.


    How FaceElements introduce additional unknowns into a problem

    FaceElements are used widely throughout oomph-lib to apply Neumann/flux/traction-type boundary conditions on the faces of higher-dimensional "bulk" elements. Príklady zahŕňajú:

    In all the examples listed above, the boundary conditions simply add a contribution to the elements' residuals but they do not introduce any additional unknowns into the problem.

    FaceElements may also be used to apply boundary conditions via Lagrange multipliers. An example is given in the tutorial that discusses

    In such problems, the Lagrange multipliers must be determined as part of the solution, and storage for the associated discrete unknowns is created at the nodes of the FaceElements .

    To explain the relevant details of the implementation we consider a simple 2D Navier-Stokes problem discretised using nine-node Taylor-Hood elements (in these elements each vertex node stores two discrete velocities and one pressure the other nodes store only two velocity degrees of freedom). We assume that boundaries 0 and 1 are subject to boundary conditions imposed via FaceElements , and that each boundary condition introduces its own Lagrange multipliers fields. [Yes, the plural is correct. As an example, consider the case of imposing displacement constraints in a 2D solid mechanics problem via Lagrange multipliers. In this approach the imposition of the boundary condition requires dva Lagrange multipliers along each constrained boundary. Physically, the Lagrange multipliers represent the two components of the surface traction required to deform the boundary into the required shape see the relevant solid mechanics problem for details.]

    The sketch below shows the discretisation of the domain, with the black circles representing the nodes. The enlargement of the top right corner also shows the discrete unknowns (nodal velocities and pressures) stored at each node after the creation of the "bulk" Navier-Stokes elements.

    The next figure shows the nodal degrees of freedom after the FaceElements on boundary 0 (shown in red) have been attached. The FaceElements share the existing nodes of the underlying "bulk" elements and automatically create storage for any additional nodal unknowns. Here we provide storage for two discrete Lagrange multipliers, a Provided that a single FaceElement is attached to a node, the function

    can be used to determine the number of nodal values at the FaceElement's j -th node created by the underlying "bulk" element predtým the FaceElement was attached. It is then easy to identify the additional nodal values associated with the FaceElement in order to apply the boundary conditions for the Lagrange multipliers, say. The methodology is illustrated in the the solid mechanics problem referred to earlier.

    The next figure shows the degrees of freedom after the FaceElements on boundary 1 (shown in green) have also been attached. These FaceElements must create storage for their own two Lagrange multipliers, a . Thus, the corner node (which is attached to both types of FaceElements ) has four additional degrees of freedom after all the FaceElements have been created.

    The identification of the additional degrees of freedom via a simple offset from the degrees of freedom created by the "bulk" element is now no longer possible. We therefore provide an alternative mechanism to access the relevant information from the nodes themselves via the function

    which does exactly what it says. If only a single type of FaceElement is attached to a (boundary) node, the unsigned that is returned by this function is exactly the same as the unsigned that is returned by the corresponding call to FaceElement::nbulk_value (. ). To cater for the case where multiple FaceElements are attached to the same node, the above function can take an ID (which defaults to zero) that identifies which type of FaceElement we are dealing with, so the full interface is, in fact,

    The ID must be established by the user, typically when the constructor of the specific FaceElement is called. It can then be passed on to the Nodes when the number of values at the nodes is adjusted to accommodate the additional values required by the FaceElement .

    To illustrate this, the code extract shown below provides a (partial) listing of the constructor of the ImposeDisplacementByLagrangeMultiplierElement that was used in the solid mechanics problem referred to earlier. The constructor has the usual two arguments that specify the pointer to the "bulk" element, and the index of the face that the FaceElement is to be attached to. The final (optional) argument allows the specification of the ID referred to above. We store the ID in a private the element's private member data.


    Optimal Taxation in an LQ Economy¶

    In this lecture we study optimal fiscal policy in a linear quadratic setting.

    We slightly modify a well-known model of Robert Lucas and Nancy Stokey [LS83] so that convenient formulas for solving linear-quadratic models can be applied to simplify the calculations.

    The economy consists of a representative household and a benevolent government.

    The government finances an exogenous stream of government purchases with state-contingent loans and a linear tax on labor income.

    A linear tax is sometimes called a flat-rate tax.

    The household maximizes utility by choosing paths for consumption and labor, taking prices and the government’s tax rate and borrowing plans as given.

    Maximum attainable utility for the household depends on the government’s tax and borrowing plans.

    The Ramsey problem [Ram27] is to choose tax and borrowing plans that maximize the household’s welfare, taking the household’s optimizing behavior as given.

    There is a large number of competitive equilibria indexed by different government fiscal policies.

    The Ramsey planner chooses the best competitive equilibrium.

    We want to study the dynamics of tax rates, tax revenues, government debt under a Ramsey plan.

    Because the Lucas and Stokey model features state-contingent government debt, the government debt dynamics differ substantially from those in a model of Robert Barro [Bar79].

    The treatment given here closely follows this manuscript, prepared by Thomas J. Sargent and Francois R. Velde.

    We cover only the key features of the problem in this lecture, leaving you to refer to that source for additional results and intuition.