Mnożniki Lagrange’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Mnożniki Lagrange'a)
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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

\left\{\begin{array}{l}f^\prime(x)=\Lambda\circ G^\prime(x)\\G(x)=0\end{array}\right.,

gdzie \Lambda\in (\mathbb{R}^m)^\star. Wiadomo, że każdy taki funkcjonał \Lambda jest reprezentowany przez układ m liczb rzeczywistych \lambda_1,\ldots,\lambda_m a pochodna G^\prime(x) jest macierzą wymiaru m\times n rzędu m[1]. Układ równań operatorowych sprowadza się więc do układu m+n równań skalarnych:

\left\{\begin{array}{l}\frac{\partial f(x)}{\partial x_j}=\sum_{i=1}^m\lambda_i\frac{\partial G_i(x)}{\partial x_j},\; j=1,\ldots,n\\G_k(x_1,\ldots, x_n)=0,\; k=1,\ldots, m\end{array}\right.,

gdzie x=(x_1,\ldots,x_n) o n+m zmiennych \lambda_i, x_k, \; i\leqslant m, k\leqslant 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^{\prime\prime}(x)-\Lambda\circ G^{\prime\prime}(x)

dla

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

co sprowadza się do badania formy kwadratowej

\sum_{i,j=1}^n\left(\frac{\partial^2f(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}\right)h_ih_j,

gdzie

h\in X_1, h=(h_1, \ldots, 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,\ldots, m.

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

W praktyce, gdy X=\mathbb{R}^2, Y=\mathbb{R} 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[2], tj. rozwiązaniu układu równań F^\prime_x=0, F^\prime_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ń

\left\{\begin{array}{l}\frac{D(f,G)}{D(x,y)}=0\\G(x,y)=0\end{array}\right.,

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

Przykład – ekstrema funkcji na okręgu[edytuj | edytuj kod]

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:

F(x,y)=f(x,y)+\lambda G(x,y)=
=x+y + \lambda (x^2 + y^2 - 1).

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

\left\{\begin{array}{ll}
F^\prime_x(x,y)= 1 + 2 \lambda x &= 0 \\
F^\prime_y(x,y)= 1 + 2 \lambda y &= 0 \\
G(x,y) = x^2 + y^2 - 1 &= 0\end{array}\right..

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

  • minimum warunkowe: f\left( -\tfrac{\sqrt{2}}{2}, -\tfrac{\sqrt{2}}{2}\right) =-\sqrt{2}
  • maksimum warunkowe: f\left( \tfrac{\sqrt{2}}{2}, \tfrac{\sqrt{2}}{2}\right) =\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[edytuj | edytuj kod]

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

f(p_1,p_2,\ldots,p_n) = -\sum_{k=1}^n p_k\log_2 p_k.

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

G(p_1,p_2,\ldots,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,\ldots,p_n)+\lambda (G(p_1,p_2,\ldots,p_n)))=0,\;\; 1\leqslant k\leqslant n,

który sprowadza się do układu

\frac{\partial}{\partial p_k}\left(-\sum_{k=1}^n p_k \log_2 p_k + \lambda (\sum_{k=1}^n p_k - 1) \right) = 0,\;\; 1\leqslant k\leqslant n.

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

-\left(\frac{1}{\ln 2}+\log_2 p_k \right) + \lambda = 0,\;\; 1\leqslant k\leqslant n.

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

p_k=\frac{1}{n}.

Zastosowania[edytuj | edytuj kod]

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.

Przypisy

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]