Pamparaming Lagrange

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin
Pigurang 1: Hanapin ang x at y upang i-maxima(maximize) ang f(x,y) na nasa ilalim ng pagtatakda(ipinapakita sa pula) na g(x,y)=c.
Pigura 2: Mapang kontur ng Pigura 1. Ang pulang linya ay nagpapakita ng pagtatakdang g(x,y)=c. Ang mga asul na linya ay mga kontur f(x,y). Ang punto kung saan ang pulang linya ay tanhensiyal na dumadapo sa asul na kontur ang solusyon.

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

Halimbawa, tignan isaalang alang ang problema ng optimisasyon na:

i-maksima (maximize) ang f(x, y) \,
sa ilalim ng pagtatakdang(constraint) g(x, y) = c.\,

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

 \Lambda(x,y,\lambda) = f(x,y) + \lambda \cdot \Big(g(x,y)-c\Big),

kung saan ang terminong \lambda ay maaaring idagdag(added) o ibawas(subtracted). Kung ang f(x, y) ay isang maximum para sa orihinal na tinakdaang problema, kung gayon ay may umiiral na  \lambda kung saan ang (x,y,\lambda) 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[baguhin | baguhin ang batayan]

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) f(x, y) \,
sa ilalim ng pagtatakdang(constraint) g(x, y) = c.\,

Maaaring ilarawan ang linyang kontur ng f na ibinigay ng:

f(x, y)=d \,

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

Ipaglagay na tayo ay naglalakad sa kahabaan ng linyang kontur na may  g = c . Sa pangkalahatan, ang mga linyang kontur ng  f at  g ay maaaring walang katulad kaya kung susundan ang linyang kontur para sa  g = c , maaaring bagtasin(intersect) o tawirin ang mga linyang kontur ng  f . Ito ay katumbas sa pagsasabi na habang gumagalaw sa kahabaan ng linyang kontur para sa  g = c , ang halaga ng f ay maaaring magbago. Tanging kung ang linyang kontur para sa  g = c ay magtatagpo sa mga linyang kontur ng  f tangensiyal hindi natin dadagdagan o babawasan ang halaga ng  f 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 gradient ng punsiyon ay perpendikular sa mga linyang kontur, ito ay parehas ng pagsasabing ang mga gradient ng f and g ay parelolo. Kaya nais natin ang mga puntong (x,y) kung saan ang g(x,y) = c at ang

\nabla_{x,y} f = - \lambda \nabla_{x,y} g,

kung

 \nabla_{x,y} f= \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right)

at

 \nabla_{x,y} g= \left( \frac{\partial g}{\partial x}, \frac{\partial g}{\partial y} \right)

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

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

 \Lambda(x,y,\lambda) = f(x,y) + \lambda \cdot \Big(g(x,y)-c\Big),

at lutasin ang

 \nabla_{x,y,\lambda} \Lambda(x , y, \lambda)=0.

Ito ang paraan ng mga multiplayer na Lagrange. Pansinin na ang \nabla_{\lambda} \Lambda(x , y, \lambda)=0 ay nagpapahiwatig ng  g(x,y)=c.

Hindi kinakailangang ekstrema[baguhin | baguhin ang batayan]

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

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 Lagrangiano 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 gradient dahil sa ang mga sero ng magnitudo ay kinakailangang lokal na minima.

Paghawak ng maraming mga pagtatakda[baguhin | baguhin ang batayan]

Isang paraboloid, ilang mga hanay na lebel(o linyang kontur) at 2 linyang pagtatakda.
Kung palalaking ang mga hanay na lebel at pagtatakda, ating makikita na ang dalawang linyang pagtatakda ay bumabagtas upang bumuo ng magkasanib na pagtatakda na isang punto. Dahil sa mayroon lamang isang putno na susuriin, ang kaakibat na punto sa paraboloid ay automatikong isang maximum at minimum. Gayunpaman, ang pinasimpleng pangangatwirang isinadd sa mga seksiyon sa itaas ay tila nabibigo dahil sa ang hanay na lebel ay lumalabaw na tumatawid sa punto at sa kasabay nito ang gradient nila ay hindi paralelo sa mga gradient ng anumang pagtatakda. Ito ay nagpapakitang kailangan nating pinuhin ang paliwanag ng paraan upang pakitunguhan ang mga uri ng pagtatakda na nabubuo kung mayroon tayong higit sa isang pagtatakda na umaasal ng sabay.

Ang paraan ng mga multiplayer na Lagrange ay maaari ring makitungo sa mga pangmaramihang mga pagtatakda. Upang makita kung paano ito gawin, kailangang muling siyasatin ang problema sa medyo ibang paraan dahil ang konsepto ng "pagtawid" na tinalakay sa taas ay nagiging mabilis na hindi maliwanag kung ating isasaalang-alang mga uri ng pagtatakda na nalilikha kung mayroon tayong higit sa isang pagtatakda na sabay sabay na umaasal. Bilang halimbawa, isaalang alan ang paraboloid na may pagtatakdang isang punto(na maaaring malikha kung may dalawa tayong linyang pagtatakda na nag-uugnayan). Ang hanay na lebel(i.e., linyang kontur) ay maliwanag na lumalabas na tumatawad sa punto ito at ang gradient ay maliwanag na hindi paralelo sa mga gradient ng kahit sa anumang dalawang pagtatakdang linya. Gayunpaman, malinaw na ito ay maximum at minimum dahil may isa lamang punto sa paraboloid na sumasalubong sa pagtatakda.

Bagaman ang halimbawang ito ay tila medyo kakaiba, ito ay madaling maunawaan at kumakatawan sa uri ng epektibong pagtatakda na lumilitaw ng malimit kung makikitungo sa mga nagbabagtasang(intersecting) maraming mga pagtatakda.

Sa buong seksiyon na ito, ang independiyenteng mga bariabulo ay tutukuying ng x_1,x_2,\ldots ,x_N at bilang isang pangkat ay tutukuyin ang mga ito na p=\left( x_1,x_2,\ldots ,x_N \right). Gayundin, ang punsiyong sinusuri ay tutukuyin na f\left( p \right) at ang mga pagtatakda ay ikakatawan ng mga ekwasyon na g_{1}\left( p \right) = 0,g_{2}\left( p \right) = 0,\,\,\ldots ,g_{M}\left( p \right) = 0.

Ang basikong ideya ay nanatiling pareho. Kung ating isaalang alang lang ang mga punto na sumasapat sa mga pagtatakda o "nasa" mga pagtatakda, kung gayon, ang puntong \left( p,f\left( p \right) \right) ay isang stasyonaryong punto o isang punto na nasa "patag" na rehiyon ng f kung at tanging kung ang mga pagtatakda sa puntong ito ay hindi pumapayag ng paggalaw s a direksiyon kung saan ang f ay hindi nagbabago ng halaga.

Kapag natukoy na ang mga stasyonaryong punto, kailangan tayong magsagawa ng mga karagdagang pagsubok upang makita kung atin nang natuklasan ang minimum, maximum o isa lamang stasyonaryong punto na wala sa mga ito.

Ating sisimulan ang pagsasaalang-alang ng hanay na lebel ng f sa \left( p,f\left( p \right) \right). Ang hanay ng mga bektor na \left\{ v_{L} \right\} na naglalaman ng mga direksiyon kung saan tayo maaaring makagalawa at mananatili pa rin sa parehong lebel ang mga direksiyon kung saan ang f ay hindi nagbabago o ang pagbabago ay katumbas ng sero. Kaya, sa bawat bektor na v sa \left\{ v_{L} \right\} ang sumusunod na ugnayan ay dapat totoo:

\Delta f=\frac{df}{dx_{1}}v_{x_{1}}+\frac{df}{dx_{2}}v_{x_{2}}+\,\,\,\cdots \,\,\,+\frac{df}{dx_{N}}v_{x_{N}}=0

kung saan ang notasyong v_{x_{K}} sa taas ay nangangahulugang ang bahaging x_{K} ng bektor na v. Ang ekwasyon sa itaas ay maaaring muling isulat sa mas siksik na heometrikong anyo na makakatulong sa ating intwisyon:

\begin{matrix}
   \underbrace{\begin{matrix}
   \left[ \begin{matrix}
   \frac{df}{dx_{1}}  \\
   \frac{df}{dx_{2}}  \\
   \vdots   \\
   \frac{df}{dx_{N}}  \\
\end{matrix} \right]  \\
   {}  \\
\end{matrix}}_{\nabla f} & \centerdot  & \underbrace{\begin{matrix}
   \left[ \begin{matrix}
   v_{x_{1}}  \\
   v_{x_{2}}  \\
   \vdots   \\
   v_{x_{N}}  \\
\end{matrix} \right]  \\
   {}  \\
\end{matrix}}_{v} & =\,\,0  \\
\end{matrix}\,\,\,\,\,\,\,\,\,\,\,\,\Rightarrow \,\,\,\,\,\,\,\,\nabla f\,\,\,\centerdot \,\,\,\,v\,\,=\,\,\,0

Ginagawa nitong maliwanag na kung tayo ay nasa p, kung gayon ang lahat ng mga direksiyon mula sa puntong ito na hindi nagbabgo ng halaga ng f ay dapat perpendikular sa \nabla f\left( p \right)(ang gradient ng f sa p).

Ngayon, ating isaalang alang ang epekto ng mga pagtatakda. Ang bawat pagtatakda ay naglilimitas ng mga direksiyon na maaari nating galawan mula sa isang partikular na punto at maari pa ring masapatan ang pagtatakda. Maaari nating gamitin ang parehong pamamaraan upang maghanap ng hanay ng mga bektor na \left\{ v_{C} \right\} na naglalaman ng mga direksiyon na maaari nating galawan at masasapatan pa rin ang pagtatakda. Gaya ng sa itaas, sa bawat bektor na v in \left\{ v_{C} \right\}, ang sumusunod na ugnayan ay dapat totoo:

\Delta g=\frac{dg}{dx_{1}}v_{x_{1}}+\frac{dg}{dx_{2}}v_{x_{2}}+\,\,\,\cdots \,\,\,+\frac{dg}{dx_{N}}v_{x_{N}}=0\,\,\,\,\,\,\,\,\,\,\,\,\,\Rightarrow \,\,\,\,\,\,\,\,\,\,\,\nabla g\,\,\centerdot \,\,\,v\,\,=\,\,\,0

Mula dito, makikita nating sa puntong p, ang lahat ng mga direksiyon mula sa puntong ito na sasapat pa rin sa pagtatakdang ito ay dapat perpendikular sa \nabla g\left( p \right) .

Ngayon, handa na tayong pinuhin pa ang ating ideya ng karagdagan at kompletuhin ang paraan: ang isang punto sa f ay isang natatakdaang stasyonaryong punto kung at tanging kung ang direksiyon na nagbabago ng f ay lumalabag sa hindi bababa sa isa sa mga pagtatakda. Makikita nating ito ay totoo dahil kung ang direksiyon na nagbabago ng f ay hindi lumabag sa anumang mga pagtatakda, kung gayon ay may legal na puntong na malapit na may mas mataas o mas mababang halaga para sa f at ang kasalukuyang punto ay kung gayon magiging stasyonaryong punto.

Muling pagbisita sa isang pagtatakda[baguhin | baguhin ang batayan]

Para sa isang pagtatakda, gagamitin nating ang pangungusap sa itass upang sabihing sa mga stasyonaryong punto, ang direksiyon na nagbabago ng f ay nasa parehong direksiyon na lumalabag sa pagtatakda. Upang matukoy kung ang dalawang bektor ay nasa parehong direksiyon, ating tatandaan na kung ang dalawang mga bektor ay nagmula sa parehong punto at nasa parehong direksiyon, kung gayon, ang isang bektor ay palaging umabot sa isa pa sa pamamagitan ng pagbabago ng haba nito o pagbabaliktad ng punto sa kabaligtarang paraan sa kahabaan ng parehong direksiyon na linya. Sa paraang ito, ating maisasaad na ang dalawang mga bektor ay tumuturo sa parehong direksiyon kung at tanging kung ang isa sa mga ito ay pinarami(multiplied) ng isang real na bilang sa paraang ang mga ito ay magiging magkatumbas sa isa't isa. Kaya para sa ating nilalayon, ating iaatas na:

\nabla f\left( p \right)=\lambda \, \nabla g\left( p \right) \qquad \Rightarrow \qquad \nabla f\left( p \right)-\lambda \, \nabla g\left( p \right)\,\,=\,\,0

Kung ating idadagdag ang isa pang kasabay na ekwasyon upang magarantiya na atin lamang isasagawa ang pagsubok na ito kung tayo ay nasa puntong sasapat sa pagtatakda, tayo ay magwawakas sa 2 sabay na mga ekwasyon na kung nalutas ay tutukoy ng lahat ng mga tinakdaang stasyonaryong mga punto:

\begin{cases}
   g\left( p \right)=0 & \text{means point satisfies constraint}  \\
   \nabla f\left( p \right)-\lambda \, \nabla g\left( p \right) = 0 & \text{means point is a stationary point}
\end{cases}

Pansinin na ang nasa itaas ay isang maikling paraan ng pagsusulat ng mga ekwasyon. Kung buong palalawigin, may mga \text{N}+\text{1} na magkasabay na mga ekwasyong kailangang lutasin para sa \text{N}+\text{1} bariabulo na \lambda and x_1,\ x_2, \ldots, x_N:

\begin{align}
g\left( x_1, x_2, \ldots , x_N \right) & =0 \\
\frac{df}{dx_1}\left( x_1, x_2, \ldots, x_N \right) - \lambda \frac{dg}{dx_1}\left( x_1, x_2,\ldots , x_N \right) & = 0 \\
\frac{df}{dx_2}\left( x_1, x_2, \ldots , x_N \right) - \lambda \frac{dg}{dx_2}\left( x_1, x_2, \ldots, x_N \right) & = 0 \\
 & {}\ \  \vdots  \\
\frac{df}{dx_N}\left( x_1, x_2, \ldots  x_N \right) - \lambda \frac{dg}{dx_N}\left( x_1, x_2, \ldots, x_N \right) & = 0
\end{align}

Pangmaramihang mga pagtatakda[baguhin | baguhin ang batayan]

Para sa higit sa isang pagtatakda, ang parehong pangangatwiran ay lumalapat. Kung may higit sa isang pagtatakda na sabay na aktibo, ang bawat pagtatakda ay nag-aambag sa direksiyon na lalabag dito. Kung pagsasamahin, ang mga paglabag at direksiyon na ito ay bubuo ng epasyong paglabag kung saan ang inpinitesimal na paggalaw sa anumang direksiyon sa loob ng espasyo ay lalabag sa isa o maraming mga pagtatakda. Kaya, upang masapatan ang maraming mga pagtatakda, maaari nating isaad na sa mga stasyonaryong punto, ang direksiyon na nagbabago ng f ay nasa paglabag na espasyo na nilikha ng mga pagtatakdang sabay na umaasal.

Ang espasyong paglabag na nilikha ng mga pagtatakda ay binubuo ng lahat ng mga punto na maaaring maabot sa pamamagitan ng pagdaragdag ng anumang kombinasyon ng may iskala o binaligtad na mga bersiyon ng indibidwal na paglabag na direksiyong mga bektor. Sa ibang salita, ang lahat ng mga punto ay maaabot kung tayo ay gagamit ng indibidwal na paglabag na mga direksiyon bilang basehan ng espasyo. Kaya, maaari na nating maikling maisaad na ang v ay nasa espasyong inilarawan ng b_1, b_2, \ldots ,b_M kung at tanging kung may umiiral na hanay ng mga multiplayer na \lambda_1, \lambda_2, \ldots , \lambda_M na:

\sum\limits_{k=1}^M \lambda_k b_k = v

na sa ating mga layunin ay maisasalin sa pagsasaad na ang direksiyong nagbabago ng f sa p ay nasa paglabag na espasyong inilalarawan ng mga pagtatakdang g_1,g_2, \ldots, g_M kung at tanging kung:

\sum_{k=1}^M  \lambda_k \nabla g_k (p) = \nabla f(p) \quad \Rightarrow \quad \nabla f(p) -  \sum_{k=1}^M {\lambda_k \nabla g_k (p)} = 0

Gaya ng sa una, ating idagdag ang sabay na ekwasyon upang magarantiya na atin lamang isasagawa ang pagsubok na ito kung tayo ay nasa puntong sasapat sa bawat pagtatakda, tayo ay magwakasa sa mga magkasabay na ekwasyon na kung nalutas ay tutukoy sa lahat ng mga tinatakdaang stasyonaryong mga punto:

\begin{matrix}
   \begin{align}
g_1(p) & = 0  \\
g_2(p)& =0 \\
& \ \ \vdots  \\
g_M(p) &= 0 \\
 &  \\
\nabla f(p) - \sum_{k=1}^M {\lambda_k \, \nabla g_k (p)} & = 0 \\
\end{align} & \begin{align}
  & \text{ang ibig sabihin nito ang punto ay sumasapat sa lahat ng mga pagtatakda} \\
 &  \\
 &  \\
 &  \\
 &  \\
 & \text{ang ibig sabihin nito ang punto ay isang stasyonaryong punto} \\
\end{align}  \\
\end{matrix}

Ang paraang ito ay kumpleto na ngayon mula sa pananaw ng paglutas ng problema ng paghahanap ng mga stasyonaryong punto ngunit sa kinagagalakang gawin ng mga matematiko, ito ay karagdagan pang mapapaliit sa mas elegant at maikling anyo. Maaaring matalinong napansin ni Lagrange na ang mga ekwasyon sa itaas ay mukhang mga parsiyal na deribatibo ng ilang mas malaking mga skalar na punsiyong L na kumukuha ng lahat ng x_1, x_2, \ldots, x_N at lahat ng \lambda _1, \lambda_2, \ldots, \lambda _M bilang mga input. Sunod nito, maaaring napansin niyang ang pagtatakda ng bawat ekwasyon na katumbas ng sero ang eksaktong ang gagawin upang malutas ang hindi tinatakdaang mga stasyonaryong mga punto ng mas malaking punsiyon. Sa pinakahuli, kanyang naipakita na ang mas malaking punsiyong L na may mga parsiyal na deribatibong eksaktong ating kailangan ay maaaring likhain ng napaka simple gaya ng:


\begin{align}
& {} \quad L\left( x_1, x_2, \ldots , x_N, \lambda_1, \lambda_2, \ldots, \lambda _M \right) \\
& = f\left( x_1, x_2, \ldots, x_N \right) - \sum\limits_{k=1}^M {\lambda_k g_k\left( x_1, x_2, \ldots , x_N \right)}
\end{align}

Sa paglutas ng ekwasyon sa itaas para sa hindi tinatakdaang mga stasyonaryong punto ay lumilikha ng eksaktong parehong mga punto gaya ng paglutas para sa mga tinatakdaang stasyonaryong punto ng f sa ilalim ng mga pagtatakdang g_1,g_2, \ldots, g_M.

Bilang parangal kay Lagrange, ang punsiyon sa itaas ay tinatawag na Lagrangian, ang mga skalar na \lambda_1, \lambda_2, \ldots, \lambda_M ay tinatawag na Mga Mutliplayer na Lagrange(Lagrange Multipliers) at ang paraang optimisasyong ito ay tinatawag na "Ang paraan ng mga Multiplayer na Lagrange". Ang paraan ng mga multiplayer na Lagrange ay nilalahat ng Mga kondisyong Karush–Kuhn–Tucker na maaaring magsaalang alan ng mga pagtatakdang inekwalidad(hindi magkatumbas) na may anyong h(x) ≤ c.

Mga halimbawa[baguhin | baguhin ang batayan]

Lagrange very simple.jpg

Unang halimbawa[baguhin | baguhin ang batayan]

Ipagpalagay na nais i-maksima ang f(x,y)=x+y na nasa ilalim ng pagtatakdang x^2+y^2=1. Ang posibleng hanay ng unit na bilog at hanay na lebel ng f ay mga linyang diagonal (na may lihis na -1), kaya makikita sa larawan sa kanan na ang maksimum ay umiiral sa (\sqrt{2}/2,\sqrt{2}/2), at ang minimum ay umiiral sa(-\sqrt{2}/2,-\sqrt{2}/2).

Sa pormal na paglalarawan, itakda ang g(x,y)-c=x^2+y^2-1, at

\Lambda(x, y, \lambda) = f(x,y) + \lambda(g(x,y)-c) = x+y +  \lambda (x^2 + y^2 - 1)

Itakda ang deribatibong d\Lambda=0 na magbibigay ng sistema ng mga ekwasyon na:

\begin{align}
\frac{\partial \Lambda}{\partial x}       &= 1 + 2 \lambda x &&= 0, \qquad \text{(i)} \\
\frac{\partial \Lambda}{\partial y}       &= 1 + 2 \lambda y &&= 0, \qquad \text{(ii)} \\
\frac{\partial \Lambda}{\partial \lambda} &= x^2 + y^2 - 1   &&= 0, \qquad \text{(iii)}
\end{align}

Gaya ng palagi, ang \partial \lambda ekwasyong((iii) dito) ang original na pagtatakda.

Kung pagsasamahin ang dalawang mga ekwasyon, ito ay magbibigay ng x=y (sa hayagan ang \lambda \neq 0, kundi ang (i) ay magbibigay 1 = 0, kaya meron tayongx=-1/(2\lambda)=y).

Kung ihahalili sa (iii), ito ay magbibigay ng 2x^2=1, kaya ang x=y=\pm \sqrt{2}/2 at \lambda = \mp \sqrt{2}/2 na nagpapakitang ang mga stasyonaryong punto ay (\sqrt{2}/2,\sqrt{2}/2) at (-\sqrt{2}/2,-\sqrt{2}/2). Kung lulutasin ang obhektibong punsiyong f sa mga ito ay magbibigay ng

f(\sqrt{2}/2,\sqrt{2}/2)=\sqrt{2}\mbox{ and } f(-\sqrt{2}/2, -\sqrt{2}/2)=-\sqrt{2},

kaya ang maksimum ay \sqrt{2} na nakamit sa (\sqrt{2}/2,\sqrt{2}/2), at ang minimum ay -\sqrt{2} na nakamit sa (-\sqrt{2}/2,-\sqrt{2}/2).

Ikalawang halimbawa[baguhin | baguhin ang batayan]

Ipagpalagay na nais nating hanapin ang mga halagang maksimum ng

 f(x, y) = x^2 y \,

na may kondisyong ang mga koordinatong x at y ay nasa bilog sa palibos ng pinagmula(origin) na may radyus na √3 na nasa ilalim ng pagtatakdang

 g(x,y) = x^2 + y^2 = 3. \,

Dahil sa may isa lamang pagtatakda ay gagamit tayo ng isa lamang pamparami na λ.

Ang pagtatakdang g(xy)-3 ay katulad ng sero sa bilog ng radyus na √3. Kaya anumang pamparami(multiple) ng g(xy)-3 ay maaaring idagdag sa f(xy) nag nag-iiwan sa f(xy) na hindi nabago sa rehiyon pinag-iinteresan(sa itaas ng bilog nang ating orihinal na pagtatakda ay nasasapatan). Itakda ang:

\Lambda(x, y, \lambda) = f(x,y) + \lambda (g(x, y)-3) = x^2y +  \lambda (x^2 + y^2 - 3). \,

Ang mga kritikal na halaga ng \Lambda ay umiiral kung ang gradient nito ay sero. Ang mga parsiyal na deribatibo ay:

\begin{align}
\frac{\partial \Lambda}{\partial x}       &= 2 x y + 2 \lambda x &&= 0, \qquad \text{(i)} \\
\frac{\partial \Lambda}{\partial y}       &= x^2 + 2 \lambda y   &&= 0, \qquad \text{(ii)} \\
\frac{\partial \Lambda}{\partial \lambda} &= x^2 + y^2 - 3       &&= 0. \qquad \text{(iii)}
\end{align}

Ang ekwasyong (iii) ay isa lamang orihinal na pagtatakda. Ang ekwasyong (i) ay nagpapahiwatig na ang  x = 0 o λ = −y. Sa unang kaso, kung ang x = 0 kung gayon ay dapat mayroon tayong y = \pm \sqrt{3} sa pamamagitan (iii) at sa pamamagitan ng (ii) ay λ = 0. Sa ikalawang kaso, kung ang λ = −y at kung ihahali sa ekwasyong (ii) meron tayong:

x^2 - 2y^2 = 0. \,

Pagkatapos ay ang x2 = 2y2. Kung ihahalili sa ekwasyong (iii) at lulutasin ang y ay magbibigay ng halagang ito ng y:

y = \pm 1. \,

Kaya mayroon anim na mga kritikal na puntong:


 (\sqrt{2},1); \quad (-\sqrt{2},1); \quad (\sqrt{2},-1); \quad (-\sqrt{2},-1); \quad (0,\sqrt{3}); \quad (0,-\sqrt{3}).

Kung lulutasin ang nilalayong punsiyon sa mga puntong ito, ating matatagpuang


 f(\pm\sqrt{2},1) = 2; \quad f(\pm\sqrt{2},-1) = -2; \quad f(0,\pm \sqrt{3})=0.

Kaya ang nilalayong punsiyon(objective funtion) ay nagkakamit ng global na maksimum(sa ilalim ng mga pagtatakda) sa (\pm\sqrt{2},1) at ang global na minimum sa (\pm\sqrt{2},-1). Ang puntong (0,\sqrt{3}) ay isang lokal na minimum at ang (0,-\sqrt{3}) ay isang lokal na maksium na maaaring matukoy sa pagsasaalang-alang ng Matrix na Hessian ng\Lambda.

Tandaan na habang ang (\sqrt{2}, 1, -1) ay isang kritikal na punto ng \Lambda, ito ay hindi isang lokal na ekstremum. Mayroon tayong \Lambda(\sqrt{2} + \epsilon, 1, -1 + \delta) = 2 + \delta(\epsilon^2 + (2\sqrt{2})\epsilon). Sa anumang ibinigay na kapitbahayan ng (\sqrt{2}, 1, -1), maaari tayong pumili ng isang maliit na positibong \epsilon at isang maliit na \delta ng anumang senyas(sign) upang makamit ang mga halagang \Lambda na parehong mas malaki at maliit sa 2.

Mga sanggunian[baguhin | baguhin ang batayan]

  1. Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. 
  2. Vapnyarskii, I.B. (2001), "Lagrange multipliers", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1556080104, http://www.encyclopediaofmath.org/index.php?title=L/l057190 .
    • Lasdon, Leon S. (1970). Optimization theory for large systems. Macmillan series in operations research. New York: The Macmillan Company. pp. xi+523. MR337317. 
    • Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc.. pp. xiii+523. MR1888251. 
  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]. 306. Berlin: Springer-Verlag. pp. 136–193 (and Bibliographical comments on pp. 334–335). ISBN 3-540-56852-2. 
  4. Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MRdoi:[http://dx.doi.org/10.1007%2F3-540-45586-8_4 10.1007/3-540-45586-8_4 1900016.[[Digital object identifier|doi]]:[http://dx.doi.org/10.1007%2F3-540-45586-8_4 10.1007/3-540-45586-8_4]].