Mnożniki Lagrange’a

Mnożnik Lagrange’a – metoda obliczania ekstremum warunkowego funkcji różniczkowalnej wykorzystywana w teorii optymalizacji. Nazwa metody pochodzi od nazwiska matematyka Josepha Louisa Lagrange’a.

Sformułowanie i analiza problemu

Szukanie ekstremów warunkowych funkcji $f:{ℝ}^n\to ℝ,$ z warunkiem zerowania $G:{ℝ}^n\to {ℝ}^m,$ będących zarazem punktami regularnymi, sprowadza się do rozwiązania układu równań operatorowych

$\{\begin{array}{c}{f}^{\prime }(x)=\mathrm{\Lambda }\circ G^{\prime }(x)\\ G(x)=0\end{array},$

gdzie $\mathrm{\Lambda }\in ({ℝ}^m{)}^{\star }.$ Wiadomo, że każdy taki funkcjonał $\mathrm{\Lambda }$ jest reprezentowany przez układ $m$ liczb rzeczywistych ${\lambda }_1,\dots ,{\lambda }_m,$ a pochodna $G^{\prime }(x)$ jest macierzą wymiaru $m\times n$ rzędu $m$. Układ równań operatorowych sprowadza się więc do układu $m+n$ równań skalarnych:

$\{\begin{array}{cc}\frac{\partial f(x)}{\partial x_j}=\sum _{i=1}^m{\lambda }_i\frac{\partial G_i(x)}{\partial x_j},& j=1,\dots ,n\\ G_k(x_1,\dots ,x_n)=0,& k=1,\dots ,m\end{array},$

gdzie $x=(x_1,\dots ,x_n)$ o $n+m$ zmiennych ${\lambda }_i,x_k,i⩽m,k⩽n.$ Wszystkie punkty, w których funkcja może przyjmować ekstrema warunkowe, należą do zbioru rozwiązań tego układu równań. Liczby ${\lambda }_i$ spełniają tylko rolę pomocniczą i nazywane są często mnożnikami Lagrange’a. Po znalezieniu punktów spełniających warunek konieczny dla ekstremum, należy odwołać się do warunku wystarczającego, tj. zbadać dodatnią (ujemną) określoność

$f^{″}(x)-\mathrm{\Lambda }\circ G^{″}(x)$

dla

$h\in X_1=\ker G^{\prime }(x_0),$

co sprowadza się do badania formy kwadratowej

$\sum _{i,j=1}^n(\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j}-\sum _{k=1}^m{\lambda }_k\frac{{\partial }^2{G}_k(x)}{\partial x_i\partial x_j})h_i{h}_j,$

gdzie:

$h\in X_1,h=(h_1,\dots ,h_n).$

Warunek $h\in X_1$ jest równoważny równaniu

$G^{\prime }(x)h=0,$

które w postaci macierzowej przybiera formę

$\sum _{i=1}^n\frac{\partial G_k(x)}{\partial x_i}{h}_i=0,k=1,2,\dots ,m.$

Do badania określoności tej macierzy można stosować kryterium Sylvestera.

W praktyce, gdy $X={ℝ}^2,Y=ℝ$ wprowadzamy funkcję pomocniczą

$F(x,y)=f(x,y)+\lambda G(x,y)$

i szukamy dla niej warunków koniecznych na istnienie jej ekstremów, jako funkcji dwóch zmiennych, tj. rozwiązaniu układu równań $F{\text{'}}_x=0,F{\text{'}}_y=0,$ a następnie wyrugowaniu z tego układu równań czynnika nieoznaczonego $\lambda .$
Do otrzymanego warunku dołączamy warunek $G(x,y)=0.$ Równoważnie, wszystkie punkty, które mogą być ekstremami warunkowymi można wyznaczyć z układu równań

$\{\begin{array}{c}\frac{D(f,G)}{D(x,y)}=0\\ G(x,y)=0\end{array},$

gdzie $\frac{D(f,G)}{D(x,y)}$ oznacza jakobian funkcji $f$ i $G.$

Przykład – ekstrema funkcji na okręgu

Wykresem funkcji $f(x,y)=x+y$ jest płaszczyzna. W przestrzeni trójwymiarowej równanie $x^2+y^2=1$ powierzchnię boczną walca (którego podstawą jest leżący na płaszczyźnie $xy$ okrąg jednostkowy). Badanie istnienia ekstremów warunkowych sprowadza się w tym wypadku do analizy punktów ekstremalnych części wspólnej walca i płaszczyzny.

Ilustracją zastosowania metody mnożników Lagrange’a jest problem wyznaczenia ekstremów funkcji:

$f(x,y)=x+y$

na okręgu jednostkowym, tj. przy warunku

$x^2+y^2=1.$

Zatem funkcja $G$ jest postaci

$G(x,y)=x^2+y^2-1,$

a funkcja $F$ wyraża się wzorem:

$\begin{array}{cc}F(x,y,\lambda )& =f(x,y)+\lambda G(x,y)\\ & =x+y+\lambda (x^2+y^2-1).\end{array}$

Wszystkie punkty, które mogą być ekstremami warunkowymi są rozwiązaniami układu równań

$\{\begin{array}{cc}F{\text{'}}_x(x,y)=1+2\lambda x& =0\\ F{\text{'}}_y(x,y)=1+2\lambda y& =0\\ G(x,y)=x^2+y^2-1& =0\end{array}.$

Przy założeniu $x\ne 0y\ne 0$ z pierwszego równania uzyskujemy $\lambda =-\frac{1}{2x},$ analogicznie z drugiego $\lambda =-\frac{1}{2y}$ więc $x=y$ oraz dostaje się warunek $2x^2=1,$ skąd wynika $x=\pm \frac{\sqrt{2}}{2}.$ Funkcja $f$ może zatem przyjmować ekstrema tylko w punktach $(-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2}),(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2}).$ Ponieważ okrąg jest zbiorem domkniętym i ograniczonym (czyli zwartym), więc na mocy twierdzenia Weierstrassa, funkcja $f$ osiąga w tych punktach ekstrema (warunkowe):

• minimum warunkowe: $f(-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2})=-\sqrt{2},$
• maksimum warunkowe: $f(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})=\sqrt{2}.$

Warto zauważyć, że funkcja $f,$ określona na całej płaszczyźnie (bez dodatkowego warunku) nie ma ekstremów.

Przykład – problem maksymalnej entropii

Problem polega na znalezieniu dyskretnego rozkładu zmiennej losowej maksymalizującego entropię. Funkcja entropii prawdopodobieństw $p_1,\dots ,p_n$ wyraża się wzorem

$f(p_1,p_2,\dots ,p_n)=-\sum _{k=1}^n{p}_k{\log }_2{p}_k.$

Oczywiście, suma prawdopodobieństw $p_1,\dots ,p_n$ jest równa jeden, więc warunek na $G$ przyjmuje postać

$G(p_1,p_2,\dots ,p_n)=\sum _{k=1}^n{p}_k-1.$

Stosując metodę mnożników Lagrange’a, dostajemy układ $n$ równań:

$\frac{\partial }{\partial p_k}(f(p_1,p_2,\dots ,p_n)+\lambda (G(p_1,p_2,\dots ,p_n)))=0,1⩽k⩽n,$

który sprowadza się do układu

$\frac{\partial }{\partial p_k}(-\sum _{k=1}^n{p}_k{\log }_2{p}_k+\lambda (\sum _{k=1}^n{p}_k-1))=0,1⩽k⩽n.$

Różniczkując każde wyrażenie względem $p_k,$ powyższy układ sprowadza się do poniższego:

$-(\frac{1}{\ln 2}+{\log }_2{p}_k)+\lambda =0,1⩽k⩽n.$

Z powyższego wynika, że wszystkie prawdopodobieństwa są równe, tj. $p_1=\dots =p_n,$ a ponieważ ich suma jest równa jeden, wynika stąd, że dla dowolnego $1⩽k⩽n:$

$p_k=\frac{1}{n}.$

Zastosowania

Metodę optymalizacji przy pomocy mnożników Lagrange’a powszechnie stosuje się w teorii ekonomii, na przykład w celu rozwiązania problemu wyboru konsumenta, w którym konsument maksymalizuje swoją funkcję użyteczności, tak aby nie przekroczyć ograniczenia budżetowego. Mnożniki Lagrange'a mają zastosowanie również w programowaniu nieliniowym.

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę

Linki zewnętrzne

• Ekstrema warunkowe i mnożniki Lagrange'a na portalu „Ważniak” MIM UW
• Szablon:MathWorld