Multiplicatorul Lagrange

De la Wikipedia, enciclopedia liberă

Fig. 1. Cu verde este desenat locul geometric al punctelor care satisfac restricţia g(x,y) = c. Cu albastru sunt desenate contururile lui f. Săgeţile reprezintă unghiul şi direcţia normală faţă de contur.

Î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 ca şi coeficienţi.

[modifică] 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$ .

[modifică] 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.