Pagkakaiba sa mga pagbabagong ng "Pamparaming Lagrange"

walang buod ng pagbabago
 
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.
 
==Paghawak ng maraming mga pagtatakda==
[[Image:As wiki lgm parab.png|thumb|right|300px|Isang [[paraboloid]], ilang mga hanay na lebel(o linyang kontur) at 2 linyang pagtatakda.]]
[[Image:As wiki lgm levelsets.png|thumb|right|300px|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 gradiento nila ay hindi paralelo sa mga gradiento 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 gradiento ay maliwanag na hindi paralelo sa mga gradiento 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
<math>x_1,x_2,\ldots ,x_N</math> at bilang isang pangkat ay tutukuyin ang mga ito na <math>p=\left( x_1,x_2,\ldots ,x_N \right)</math>. Gayundin, ang punsiyong sinusuri ay tutukuyin na <math>f\left( p \right)</math> at ang mga pagtatakda ay ikakatawan ng mga ekwasyon na <math>g_{1}\left( p \right) = 0,g_{2}\left( p \right) = 0,\,\,\ldots ,g_{M}\left( p \right) = 0</math>.
 
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 <math>\left( p,f\left( p \right) \right)</math> 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 <math>\left( p,f\left( p \right) \right)</math>. Ang hanay ng mga [[bektor]] na
<math>\left\{ v_{L} \right\}</math> 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 <math>\left\{ v_{L} \right\}</math> ang sumusunod na ugnayan ay dapat totoo:
: <math>\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</math>
 
kung saan ang notasyong <math>v_{x_{K}}</math> sa taas ay nangangahulugang ang bahaging <math>x_{K}</math> ng bektor na ''v''. Ang ekwasyon sa itaas ay maaaring muling isulat sa mas siksik na heometrikong anyo na makakatulong sa ating intwisyon:
 
: <math>\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</math>
 
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 <math>\nabla f\left( p \right)</math>(ang gradiento 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 <math>\left\{ v_{C} \right\}</math> 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 <math>\left\{ v_{C} \right\}</math>, ang sumusunod na ugnayan ay dapat totoo:
 
: <math>\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</math>
 
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 <math>\nabla g\left( p \right)</math> .
 
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===
 
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:
 
: <math>\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</math>
 
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:
 
: <math>\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}
</math>
 
Pansinin na ang nasa itaas ay isang maikling paraan ng pagsusulat ng mga ekwasyon. Kung buong palalawigin, may mga <math>\text{N}+\text{1}</math> na magkasabay na mga ekwasyong kailangang lutasin para sa <math>\text{N}+\text{1}</math> bariabulo na <math>\lambda </math> and <math>x_1,\ x_2, \ldots, x_N</math>:
 
: <math>\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}
</math>
 
=== Pangmaramihang mga pagtatakda ===
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 <math>b_1, b_2, \ldots ,b_M</math> kung at tanging kung may umiiral na hanay ng mga multiplayer na <math>\lambda_1, \lambda_2, \ldots , \lambda_M</math> na:
 
: <math>\sum\limits_{k=1}^M \lambda_k b_k = v</math>
 
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 <math>g_1,g_2, \ldots, g_M</math> kung at tanging kung:
 
: <math>\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</math>
 
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:
 
: <math>\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{these mean the point satisfies all constraints} \\
& \\
& \\
& \\
& \\
& \text{this means the point is a stationary point} \\
\end{align} \\
\end{matrix}</math>
 
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 <math>x_1, x_2, \ldots, x_N</math> at lahat ng <math>\lambda _1, \lambda_2, \ldots, \lambda _M</math> 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:
 
: <math>
\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}
</math>
 
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 <math>g_1,g_2, \ldots, g_M</math>.
 
Bilang parangal kay Lagrange, ang punsiyon sa itaas ay tinatawag na ''Lagrangian'', ang mga skalar na <math>\lambda_1, \lambda_2, \ldots, \lambda_M</math> 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''')&nbsp;≤&nbsp;''c''.
 
 
==Sanggunian==