Multiplicatorul Lagrange

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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[modificare | modificare sursă]

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[modificare | modificare sursă]

Fie f (x) o funcție definită ca {xRn}. Definim k restricțiile gk (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 ( gk=0), ceea ce înseamnă că f a fost extremizat.

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

Exemple[modificare | modificare sursă]

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 pi sunt egali (deoarece ei depind doar de λ ). Folosind restricția ∑k pk = 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[modificare | modificare sursă]