Mnożniki Lagrange’a

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

Sformułowanie i analiza problemu

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

${\displaystyle {\begin{cases}f'(x)=\Lambda \circ G'(x)\\[2pt]G(x)=0\end{cases}},}$

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

${\displaystyle {\begin{cases}{\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\\[2pt]G_{k}(x_{1},\dots ,x_{n})=0,&k=1,\dots ,m\end{cases}},}$

gdzie ${\displaystyle x=(x_{1},\dots ,x_{n})}$ o ${\displaystyle n+m}$ zmiennych ${\displaystyle \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 ${\displaystyle \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ść

${\displaystyle f''(x)-\Lambda \circ G''(x)}$

dla

${\displaystyle h\in X_{1}=\ker G'(x_{0}),}$

co sprowadza się do badania formy kwadratowej

${\displaystyle \sum _{i,j=1}^{n}\left({\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}}}\right)h_{i}h_{j},}$

gdzie:

${\displaystyle h\in X_{1},h=(h_{1},\dots ,h_{n}).}$

Warunek ${\displaystyle h\in X_{1}}$ jest równoważny równaniu

${\displaystyle G'(x)h=0,}$

które w postaci macierzowej przybiera formę

${\displaystyle \sum _{i=1}^{n}{\frac {\partial G_{k}(x)}{\partial x_{i}}}h_{i}=0,\quad k=1,2,\dots ,m.}$

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

W praktyce, gdy ${\displaystyle X=\mathbb {R} ^{2},Y=\mathbb {R} }$ wprowadzamy funkcję pomocniczą

${\displaystyle 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^[3], tj. rozwiązaniu układu równań ${\displaystyle F'_{x}=0,F'_{y}=0,}$ a następnie wyrugowaniu z tego układu równań czynnika nieoznaczonego ${\displaystyle \lambda .}$
Do otrzymanego warunku dołączamy warunek ${\displaystyle G(x,y)=0.}$ Równoważnie, wszystkie punkty, które mogą być ekstremami warunkowymi można wyznaczyć z układu równań

${\displaystyle {\begin{cases}{\frac {D(f,G)}{D(x,y)}}=0\\[2pt]G(x,y)=0\end{cases}},}$

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

Przykład – ekstrema funkcji na okręgu

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

${\displaystyle f(x,y)=x+y}$

na okręgu jednostkowym, tj. przy warunku

${\displaystyle x^{2}+y^{2}=1.}$

Zatem funkcja ${\displaystyle G}$ jest postaci

${\displaystyle G(x,y)=x^{2}+y^{2}-1,}$

a funkcja ${\displaystyle F}$ wyraża się wzorem:

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

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

${\displaystyle {\begin{cases}F'_{x}(x,y)=1+2\lambda x&=0\\[2pt]F'_{y}(x,y)=1+2\lambda y&=0\\[2pt]G(x,y)=x^{2}+y^{2}-1&=0\end{cases}}.}$

Przy założeniu ${\displaystyle x\neq 0\,\,y\neq 0}$ z pierwszego równania uzyskujemy ${\displaystyle \lambda =-{\tfrac {1}{2x}},}$ analogicznie z drugiego ${\displaystyle \lambda =-{\tfrac {1}{2y}}}$ więc ${\displaystyle x=y}$ oraz dostaje się warunek ${\displaystyle 2x^{2}=1,}$ skąd wynika ${\displaystyle x=\pm {\tfrac {\sqrt {2}}{2}}.}$ Funkcja ${\displaystyle f}$ może zatem przyjmować ekstrema tylko w punktach ${\displaystyle \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^[4]), więc na mocy twierdzenia Weierstrassa, funkcja ${\displaystyle f}$ osiąga w tych punktach ekstrema (warunkowe):

• minimum warunkowe: ${\displaystyle f\left(-{\tfrac {\sqrt {2}}{2}},-{\tfrac {\sqrt {2}}{2}}\right)=-{\sqrt {2}},}$
• maksimum warunkowe: ${\displaystyle f\left({\tfrac {\sqrt {2}}{2}},{\tfrac {\sqrt {2}}{2}}\right)={\sqrt {2}}.}$

Warto zauważyć, że funkcja ${\displaystyle 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 ${\displaystyle p_{1},\dots ,p_{n}}$ wyraża się wzorem

${\displaystyle f(p_{1},p_{2},\dots ,p_{n})=-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}.}$

Oczywiście, suma prawdopodobieństw ${\displaystyle p_{1},\dots ,p_{n}}$ jest równa jeden, więc warunek na ${\displaystyle G}$ przyjmuje postać

${\displaystyle 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 ${\displaystyle n}$ równań:

${\displaystyle {\frac {\partial }{\partial p_{k}}}(f(p_{1},p_{2},\dots ,p_{n})+\lambda (G(p_{1},p_{2},\dots ,p_{n})))=0,\quad 1\leqslant k\leqslant n,}$

który sprowadza się do układu

${\displaystyle {\frac {\partial }{\partial p_{k}}}\left(-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}+\lambda \left(\sum _{k=1}^{n}p_{k}-1\right)\right)=0,\quad 1\leqslant k\leqslant n.}$

Różniczkując każde wyrażenie względem ${\displaystyle p_{k},}$ powyższy układ sprowadza się do poniższego:

${\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{k}\right)+\lambda =0,\quad 1\leqslant k\leqslant n.}$

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

${\displaystyle 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.^[5]

Przypisy

Bibliografia

• Franciszek Leja: Rachunek różniczkowy i całkowy. Warszawa: PWN, 1976.brak strony w książce
• Krzysztof Maurin: Analiza – Część I – Elementy. Warszawa: PWN, 1976. ISBN 978-83-01-09939-8.brak strony w książce

Linki zewnętrzne

• Ekstrema warunkowe i mnożniki Lagrange'a na portalu „Ważniak” MIM UW
• Eric W.E.W. Weisstein Eric W.E.W., Lagrange Multiplier, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).