Multiplicatorul Lagrange

Î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

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

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

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

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

${\displaystyle \nabla {\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

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

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

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

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

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

care este echivalent cu:

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

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

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

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

și obținem:

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

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

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