Pamparaming Lagrange: Pagkakaiba sa mga binago

Mula sa Wikipedia, ang malayang ensiklopedya
Content deleted Content added
No edit summary
No edit summary
Linya 27: Linya 27:
{{cite book|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|chapter=XII&nbsp;Abstract duality for practitioners|title=Convex analysis and minimization algorithms, Volume&nbsp;II: Advanced theory and bundle methods|series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]|volume=306|publisher=Springer-Verlag|location=Berlin|year=1993|pages=136–193 (and Bibliographical comments on pp.&nbsp;334–335)|isbn=3-540-56852-2|{{MR|1295240}}|authorlink2=Claude Lemaréchal|}}</ref><ref>{{cite book|last=Lemaréchal|first=Claude
{{cite book|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|chapter=XII&nbsp;Abstract duality for practitioners|title=Convex analysis and minimization algorithms, Volume&nbsp;II: Advanced theory and bundle methods|series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]|volume=306|publisher=Springer-Verlag|location=Berlin|year=1993|pages=136–193 (and Bibliographical comments on pp.&nbsp;334–335)|isbn=3-540-56852-2|{{MR|1295240}}|authorlink2=Claude Lemaréchal|}}</ref><ref>{{cite book|last=Lemaréchal|first=Claude
|chapter=Lagrangian relaxation|pages=112–156|doi=10.1007/3-540-45586-8_4|title=Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May&nbsp;15–19,&nbsp;2000|editor=Michael Jünger and Denis Naddef|series=Lecture Notes in Computer Science|volume=2241|publisher=Springer-Verlag|location=Berlin|year=2001|isbn=3-540-42877-1|mr=1900016.{{doi|10.1007/3-540-45586-8_4}}|authorlink=Claude Lemaréchal|}}</ref>
|chapter=Lagrangian relaxation|pages=112–156|doi=10.1007/3-540-45586-8_4|title=Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May&nbsp;15–19,&nbsp;2000|editor=Michael Jünger and Denis Naddef|series=Lecture Notes in Computer Science|volume=2241|publisher=Springer-Verlag|location=Berlin|year=2001|isbn=3-540-42877-1|mr=1900016.{{doi|10.1007/3-540-45586-8_4}}|authorlink=Claude Lemaréchal|}}</ref>
==Introduksiyon==
Ang isa sa pinaka karaniwang mga problema sa [[kalkulo]] ang paghahanap ng [[maxima at minima]](sa pangkalahatan ay extrema) ng isang [[punsiyon]] ngunit kalimitan ay mahirap na mahanap ang isang saradong anyo para sa isang punsiyong ini-extrema. Ang gayong mga kahirapan ay kalimitang lumilitwa kung nanaisin na i-maxima o i-minima ang isang punsiyon sa ilalim ng isang nakatakdang panglabas na mga kondisyon o constraints. Ang paraan ng mga multiplayer na Lagrange ay isang makapangyarihang kasangkapan sa paglutas ng ganitong klaseng mga problema na hindi nangangailangan ng hayagang paglutas sa mga kondisyon at gagamitin ang mga ito upang tanggalin ang mga ekstrang [[bariabulo]].

Kung isasaalang alan ang dalawang dimensiyonal na problemang nasa itaas na:
:i-maxima(maximize) <math>f(x, y) \,</math>
:sa ilalim ng pagtatakdang(constraint) <math>g(x, y) = c.\, </math>

Maaaring ilarawan ang [[linyang kontur]] ng ''f'' na ibinigay ng:

:<math>f(x, y)=d \,</math>

para sa iba ibang mga halaga ng <math> d </math> at ang kontur ng <math> g </math> na ibinigay ng <math> g ( x, y ) = c </math>.

Ipaglagay na tayo ay naglalakda sa kahabaan ng linyang kontur na may <math> g = c </math>. Sa pangkalahatan, ang mga linyang kontur ng <math> f </math> at <math> g </math> ay maaaring walang katulad kaya kung susundan ang linyang kontur para sa <math> g = c </math>, maaaring bagtasin(intersect) o tawirin ang mga linyang kontur ng <math> f </math>. Ito ay katumbas sa pagsasabi na habang gumagalaw sa kahabaan ng linyang kontur para sa <math> g = c </math>, ang halaga ng <math>f </math> ay maaaring magbago. Tanging kung ang linyang kontur para sa <math> g = c </math> ay magtatagpo sa mga linyang kontur ng <math> f </math> [[pagdidikit (matematika) (mathematics)|tangensiyal] hindi natin dadagdagan o babawasan ang halaga ng <math> f </math> na ang ibig sabihin ay kung ang mga linyang kontur ay nagdadapuan ngunit hindi nagtatawiran.

Ang mga linyang kontur ng ''f'' at ''g'' ay nagdadapuan kung ang mga [[bektor na tangent]] ng mga linyang kontur ay [[paralelo]]. Dahil sa ang [[gradiento]] ng punsiyon ay [[perpendikular]] sa mga linyang kontur, ito ay parehas ng pagsasabing ang mga gradiento ng ''f'' and ''g'' ay parelolo. Kaya nais natin ang mga puntong <math>(x,y)</math> kung saan ang <math>g(x,y) = c</math> at ang
:<math>\nabla_{x,y} f = - \lambda \nabla_{x,y} g</math>,
kung
:<math> \nabla_{x,y} f= \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) </math>
at
:<math> \nabla_{x,y} g= \left( \frac{\partial g}{\partial x}, \frac{\partial g}{\partial y} \right) </math>

ang mga respektibong gradiento. Ang [[konstante]]ng <math>\lambda</math> ay kailangan dahil bagaman ang dalawang mga bektor na gradiento ay paralelo, ang mga [[magnitudo]] ng mga bektor na gradiento ay sa pangkalahatan hindi magkatumbas.

Upang pagsamahin ang mga kondisyon ito sa isang [[ekwasyon]], ating ipakikilala ang isang katulong na punsiyong
:<math> \Lambda(x,y,\lambda) = f(x,y) + \lambda \cdot \Big(g(x,y)-c\Big), </math>
at lutasin ang
:<math> \nabla_{x,y,\lambda} \Lambda(x , y, \lambda)=0. </math>
Ito ang paraan ng mga multiplayer na Lagrange. Pansinin na ang <math>\nabla_{\lambda} \Lambda(x , y, \lambda)=0</math> ay nagpapahiwatig ng <math> g(x,y)=c</math>.

=== Hindi kinakailangang extrema===

Ang tinatakdaang extrema ng <math>f</math> ang mga [[kritikal na punto]] ng Lagrangian na <math>\Lambda</math> ngunit ang mga ito ay hindi lokal na extrema ng <math>\Lambda</math>.

Maaaring [[Repormulasyon ng Lagrangian mekaniks|muling ipormula ang Lagrangian]] bilang isang [[Mekaniks na Hamiltonian|Hamiltonian]] na ang kasong ang mga solusyon ang mga lokal na minima para sa Hamiltonian. Ito ay ginagawa sa teoriyang [[optimal na kontrol]] sa anyo ng [[Prinsipyong minimum ni Pontryagin]].

Ang katotohanan ang mga solusyon ng Lagrangian ay hindi rin kinakailangang extrema ay nagbibigay rin kahirapan para sa numerikal na optimisasyon. Ito ay maaaring matugunan sa pamamagitan ng pagkukwenta ng magnitudo ng gradiento dahil sa ang mga sero ng magnitudo ay kinakailangang lokal na minima.


==Sanggunian==
==Sanggunian==
{{reflist}}
{{reflist}}

Pagbabago noong 19:14, 18 Disyembre 2011

Pigurang 1: Hanapin ang x at y upang i-maxima(maximize) ang na nasa ilalim ng pagtatakda(ipinapakita sa pula) na .
Pigura 2: Mapang kontur ng Pigura 1. Ang pulang linya ay nagpapakita ng pagtatakdang . Ang mga asul na linya ay mga kontur . Ang punto kung saan ang pulang linya ay tangential na dumadapo sa asul na kontur ang solusyon.

Sa matematikal na optimisasyon, ang paraan ng mga multiplayer na Lagrange(Ingles: Lagrange multiplier) na ipinangalan kay Joseph Louis Lagrange ay nagbibigay ng stratehiya para sa paghahanap ng maxima at minima ng isang punsiyon na nasa ilalim ng mga pagtatakda(constraints).

Halimbawa, tignan isaalang alang ang problema ng optimisasyon na:

i-maxima(maximize)
sa ilalim ng pagtatakdang(constraint)

Kailangan ipakilala ang bagong bariabulo() na tinatawag na multiplayer na Lagrange at pag-aralan ang punsiyong Lagrange na inilalarawan ng:

kung saan ang terminong ay maaaring idagdag(added) o ibawas(subtracted). Kung ang ay isang maximum para sa orihinal na tinakdaang problema, kung gayon ay may umiiral na kung saan ang ay isang stasyonaryong punto para sa punsiyong Lagrange. Ang mga puntong stasyonaryo ang mga punto kung saan ang mga parsiyal na deribatibo ng Λ ay sero. Gayunpaman, hindi lahat ng mga stasyonaryong punto ay magbibigay ng solusyon sa orihinal na problema. Dahil dito, ang paraan ng mga multiplayer na Lagrange ay magbibigay ng kinakailangang kondisyon para sa optimalidad ng mga tinatakdaang problema.[1][2][3][4][5]

Introduksiyon

Ang isa sa pinaka karaniwang mga problema sa kalkulo ang paghahanap ng maxima at minima(sa pangkalahatan ay extrema) ng isang punsiyon ngunit kalimitan ay mahirap na mahanap ang isang saradong anyo para sa isang punsiyong ini-extrema. Ang gayong mga kahirapan ay kalimitang lumilitwa kung nanaisin na i-maxima o i-minima ang isang punsiyon sa ilalim ng isang nakatakdang panglabas na mga kondisyon o constraints. Ang paraan ng mga multiplayer na Lagrange ay isang makapangyarihang kasangkapan sa paglutas ng ganitong klaseng mga problema na hindi nangangailangan ng hayagang paglutas sa mga kondisyon at gagamitin ang mga ito upang tanggalin ang mga ekstrang bariabulo.

Kung isasaalang alan ang dalawang dimensiyonal na problemang nasa itaas na:

i-maxima(maximize)
sa ilalim ng pagtatakdang(constraint)

Maaaring ilarawan ang linyang kontur ng f na ibinigay ng:

para sa iba ibang mga halaga ng at ang kontur ng na ibinigay ng .

Ipaglagay na tayo ay naglalakda sa kahabaan ng linyang kontur na may . Sa pangkalahatan, ang mga linyang kontur ng at ay maaaring walang katulad kaya kung susundan ang linyang kontur para sa , maaaring bagtasin(intersect) o tawirin ang mga linyang kontur ng . Ito ay katumbas sa pagsasabi na habang gumagalaw sa kahabaan ng linyang kontur para sa , ang halaga ng ay maaaring magbago. Tanging kung ang linyang kontur para sa ay magtatagpo sa mga linyang kontur ng [[pagdidikit (matematika) (mathematics)|tangensiyal] hindi natin dadagdagan o babawasan ang halaga ng na ang ibig sabihin ay kung ang mga linyang kontur ay nagdadapuan ngunit hindi nagtatawiran.

Ang mga linyang kontur ng f at g ay nagdadapuan kung ang mga bektor na tangent ng mga linyang kontur ay paralelo. Dahil sa ang gradiento ng punsiyon ay perpendikular sa mga linyang kontur, ito ay parehas ng pagsasabing ang mga gradiento ng f and g ay parelolo. Kaya nais natin ang mga puntong kung saan ang at ang

,

kung

at

ang mga respektibong gradiento. Ang konstanteng ay kailangan dahil bagaman ang dalawang mga bektor na gradiento ay paralelo, ang mga magnitudo ng mga bektor na gradiento ay sa pangkalahatan hindi magkatumbas.

Upang pagsamahin ang mga kondisyon ito sa isang ekwasyon, ating ipakikilala ang isang katulong na punsiyong

at lutasin ang

Ito ang paraan ng mga multiplayer na Lagrange. Pansinin na ang ay nagpapahiwatig ng .

Hindi kinakailangang extrema

Ang tinatakdaang extrema ng ang mga kritikal na punto ng Lagrangian na ngunit ang mga ito ay hindi lokal na extrema ng .

Maaaring muling ipormula ang Lagrangian bilang isang Hamiltonian na ang kasong ang mga solusyon ang mga lokal na minima para sa Hamiltonian. Ito ay ginagawa sa teoriyang optimal na kontrol sa anyo ng Prinsipyong minimum ni Pontryagin.

Ang katotohanan ang mga solusyon ng Lagrangian ay hindi rin kinakailangang extrema ay nagbibigay rin kahirapan para sa numerikal na optimisasyon. Ito ay maaaring matugunan sa pamamagitan ng pagkukwenta ng magnitudo ng gradiento dahil sa ang mga sero ng magnitudo ay kinakailangang lokal na minima.


Sanggunian

  1. Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second pat.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
  2. Vapnyarskii, I.B. (2001), "Lagrange multipliers", in Hazewinkel, Michiel (pat.), Encyclopedia of Mathematics, Springer, ISBN 978-1556080104.
    • Lasdon, Leon S. (1970). Optimization theory for large systems. Macmillan series in operations research. New York: The Macmillan Company. pp. xi+523. MR 0337317.
    • Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan pat.). Mineola, New York: Dover Publications, Inc. pp. xiii+523. MR 1888251.
  3. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "XII Abstract duality for practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Bol. 306. Berlin: Springer-Verlag. pp. 136–193 (and Bibliographical comments on pp. 334–335). ISBN 3-540-56852-2. {{cite book}}: Cite has empty unknown parameter: |2= (tulong); Text "MR1295240" ignored (tulong)
  4. Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (pat.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Bol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.[[Digital object identifier|doi]]:[//dx.doi.org/10.1007%2F3-540-45586-8_4 '"`UNIQ--nowiki-00000037-QINU`"']. {{cite book}}: Check |mr= value (tulong); Cite has empty unknown parameter: |1= (tulong); External link in |mr= (tulong)