Multiplicatorul Lagrange

Acest articol se referă la Multiplicatorul Lagrange. Pentru alte sensuri, vedeți Lagrange (dezambiguizare).

În probleme de optimizare, multiplicatorii Lagrange, denumiți astfel după Joseph Louis Lagrange, sunt o metodă de lucru cu restricții. Se caută punctele de extrem ale unei funcții cu mai multe variabile și una sau mai multe restricții. Această metodă reduce o problemă cu n variabile și k restricții la o problemă rezolvabilă în n + k variabile, fără restricții. Această metodă introduce o nouă variabilă scalară, necunoscută, multiplicatorul Lagrange, pentru fiecare restricție și formează o combinație liniară cu multiplicatorii drept coeficienți.

Introducere

Considerăm cazul bidimensional. Presupunem că avem o funcție, f(x,y), pe care trebuie să o maximizăm cu condiția ca

g ( x , y ) = c , {\displaystyle g\left(x,y\right)=c,}

unde c este o constantă. Conturul lui f este dat de

f ( x , y ) = d n {\displaystyle f\left(x,y\right)=d_{n}}

pentru diferite valori ale lui d n {\displaystyle d_{n}} , iar conturul lui g {\displaystyle g} este dat de g ( x , y ) = c {\displaystyle g(x,y)=c} . Presupunem că ne mișcăm de-a lungul conturului g = c {\displaystyle g=c} . Din moment ce, în general, contururile lui f {\displaystyle f} și g {\displaystyle g} vor fi distincte, traversând g = c {\displaystyle g=c} conturul va intersecta și va traversa mai multe contururi ale lui f {\displaystyle f} . În general, mișcându-ne de-a lungul liniei g = c {\displaystyle g=c} putem crește sau descrește valoarea lui f {\displaystyle f} . Doar dacă g = c {\displaystyle g=c} , iar conturul pe care-l urmărim, atinge tangențial, dar nu traversează un contur al lui f {\displaystyle f} , nu creștem sau descreștem valoarea lui f {\displaystyle f} . Acest lucru apare la restricțiile punctelor de extrem locale și la restricțiile punctelor de inflexiune ale lui f {\displaystyle f} .

Un exemplu familiar poate fi obținut din hărțile meteorologice care au contururi pentru temperatură și presiune: restricțiile punctelor de extrem vor apărea acolo unde prin suprapunerea hărților apar linii care se ating, izoplete.

Geometric, condiția de tangență se traduce prin afirmația că unghiurile lui f {\displaystyle f} și ale lui g {\displaystyle g} sunt vectori paraleli în punctul de maxim. Introducând un scalar necunoscut, λ, obținem

∇ [ f ( x , y ) + λ ( g ( x , y ) − c ) ] = 0 {\displaystyle \nabla {\Big [}f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right){\Big ]}=0}

for λ ≠ 0.

Odată ce valorile lui λ sunt determinate, ne întoarcem la numărul original de variabile și astfel putem continua pentru a găsi punctele de extrem ale noii funcții fără restricții

F ( x , y ) {\displaystyle F\left(x,y\right)} = f ( x , y ) + λ ( g ( x , y ) − c ) {\displaystyle f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)}

într-un mod tradițional. Astfel, F ( x , y ) = f ( x , y ) {\displaystyle F(x,y)=f(x,y)} pentru toți ( x , y ) {\displaystyle (x,y)} satisfac condiția, deoarece g ( x , y ) − c {\displaystyle g(x,y)-c} este egal cu zero în restricție, însă punctele de extrem ale lui F ( x , y ) {\displaystyle F(x,y)} se află toate în g ( x , y ) = c {\displaystyle g(x,y)=c} .

Metoda multiplicatorilor Lagrange

Fie f (x) o funcție definită ca {x ∈ Rn}. Definim k restricțiile gk (x) = 0, și vedem dacă restricțiile sunt într-adevăr satisfăcute:

h ( x , λ ) = f + ∑ k λ k g k {\displaystyle h(\mathbf {x} ,\mathbf {\lambda } )=f+\sum _{k}\lambda _{k}g_{k}}

Căutăm punctul de extrem al lui h:

∂ h ∂ x i = 0 , {\displaystyle {\frac {\partial h}{\partial x_{i}}}=0,}

care este echivalent cu:

∂ f ∂ x i = − ∑ k λ k ∂ g k ∂ x i {\displaystyle {\frac {\partial f}{\partial x_{i}}}=-\sum _{k}\lambda _{k}{\frac {\partial g_{k}}{\partial x_{i}}}} .

Determinăm multiplicatorii necunoscuți λk din restricțiile noastre și obținem astfel un punct de extrem pentru h întărind restricțiile ( gk=0), ceea ce înseamnă că f a fost extremizat.

Metoda multiplicatorilor Lagrange a fost generalizată prin teorema Kuhn-Tucker.

Exemple

Presupunem că vrem să aflăm distribuția probabilistică discretă, cu entropie informațională maximă. Atunci:

f ( p 1 , p 2 , ⋯ , p n ) = − ∑ k = 1 n p k log 2 ⁡ p k {\displaystyle f(p_{1},p_{2},\cdots ,p_{n})=-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}} .

Desigur, suma acestor probabilități este egală cu 1, deci restricția noastră este:

g ( p 1 , p 2 , ⋯ , p n ) = ∑ k = 1 n p k − 1 {\displaystyle g(p_{1},p_{2},\cdots ,p_{n})=\sum _{k=1}^{n}p_{k}-1} .

Putem folosi multiplicatorii Lagrange pentru a găsi punctul entropiei maxime (depinzând de probabilități). Pentru toți i de la 1 la n, se cere ca:

∂ ∂ p i ( f + λ g ) = 0 {\displaystyle {\frac {\partial }{\partial p_{i}}}(f+\lambda g)=0} ,

și obținem:

∂ ∂ p i ( − ∑ k = 1 n p k log 2 ⁡ p k + λ ( ∑ k = 1 n p k − 1 ) ) = 0. {\displaystyle {\frac {\partial }{\partial p_{i}}}\left(-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}+\lambda (\sum _{k=1}^{n}p_{k}-1)\right)=0.}

Făcând diferențierea acestor ecuații n, obținem:

− ( 1 ln ⁡ 2 + log 2 ⁡ p i ) + λ = 0 {\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{i}\right)+\lambda =0} .

Asta arată că toți pi sunt egali (deoarece ei depind doar de λ ). Folosind restricția ∑k pk = 1, găsim

p i = 1 n {\displaystyle p_{i}={\frac {1}{n}}} .

Din aceasta rezultă că distribuția uniformă are cea mai mare entropie.

Pentru un alt exemplu, vezi derivarea funcției de partiție.

Legături externe

  • Applet Arhivat în , la Wayback Machine.
  • Tutorial and applet Arhivat în , la Wayback Machine.