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\left(x,y\right)=c,$

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

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

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

$\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\left(x,y\right)$ = $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)$ pentru toți $(x,y)$ satisfac condiția, deoarece $g(x,y)-c$ este egal cu zero în restricție, însă punctele de extrem ale lui $F(x,y)$ se află toate în $g(x,y)=c$.

Metoda multiplicatorilor Lagrange

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

$h(\mathbf {x} ,\mathbf {\lambda } )=f+\sum _{k}\lambda _{k}g_{k}$

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

${\frac {\partial h}{\partial x_{i}}}=0,$

care este echivalent cu:

${\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 ( g_k=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},\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},\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:

${\frac {\partial }{\partial p_{i}}}(f+\lambda g)=0$,

și obținem:

${\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:

$-\left({\frac {1}{\ln 2}}+\log _{2}p_{i}\right)+\lambda =0$.

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

$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 1 ianuarie 2007, la Wayback Machine.
• Tutorial and applet Arhivat în 10 noiembrie 2006, la Wayback Machine.