Mnożnik Lagrange’a – metoda obliczania ekstremum warunkowego funkcji różniczkowalnej[1] 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
:
R
n
→
R
,
{\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} ,}
G
:
R
n
→
R
m
,
{\displaystyle G\colon \mathbb {R} ^{n}\to \mathbb {R} ^{m},}
punktami regularnymi [2]
{
f
′
(
x
)
=
Λ
∘
G
′
(
x
)
G
(
x
)
=
0
,
{\displaystyle {\begin{cases}f'(x)=\Lambda \circ G'(x)\\[2pt]G(x)=0\end{cases}},}
gdzie
Λ
∈
(
R
m
)
⋆
.
{\displaystyle \Lambda \in (\mathbb {R} ^{m})^{\star }.}
funkcjonał
Λ
{\displaystyle \Lambda }
m
{\displaystyle m}
liczb rzeczywistych
λ
1
,
…
,
λ
m
,
{\displaystyle \lambda _{1},\dots ,\lambda _{m},}
G
′
(
x
)
{\displaystyle G'(x)}
macierzą wymiaru
m
×
n
{\displaystyle m\times n}
rzędu
m
{\displaystyle m}
[2]
m
+
n
{\displaystyle m+n}
{
∂
f
(
x
)
∂
x
j
=
∑
i
=
1
m
λ
i
∂
G
i
(
x
)
∂
x
j
,
j
=
1
,
…
,
n
G
k
(
x
1
,
…
,
x
n
)
=
0
,
k
=
1
,
…
,
m
,
{\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
x
=
(
x
1
,
…
,
x
n
)
{\displaystyle x=(x_{1},\dots ,x_{n})}
n
+
m
{\displaystyle n+m}
λ
i
,
x
k
,
i
⩽
m
,
k
⩽
n
.
{\displaystyle \lambda _{i},x_{k},\;i\leqslant m,k\leqslant n.}
λ
i
{\displaystyle \lambda _{i}}
warunek konieczny dla ekstremum, należy odwołać się do warunku wystarczającego , tj. zbadać dodatnią (ujemną) określoność
f
″
(
x
)
−
Λ
∘
G
″
(
x
)
{\displaystyle f''(x)-\Lambda \circ G''(x)}
dla
h
∈
X
1
=
ker
G
′
(
x
0
)
,
{\displaystyle h\in X_{1}=\ker G'(x_{0}),}
co sprowadza się do badania formy kwadratowej
∑
i
,
j
=
1
n
(
∂
2
f
(
x
)
∂
x
i
∂
x
j
−
∑
k
=
1
m
λ
k
∂
2
G
k
(
x
)
∂
x
i
∂
x
j
)
h
i
h
j
,
{\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:
h
∈
X
1
,
h
=
(
h
1
,
…
,
h
n
)
.
{\displaystyle h\in X_{1},h=(h_{1},\dots ,h_{n}).}
Warunek
h
∈
X
1
{\displaystyle h\in X_{1}}
G
′
(
x
)
h
=
0
,
{\displaystyle G'(x)h=0,}
które w postaci macierzowej przybiera formę
∑
i
=
1
n
∂
G
k
(
x
)
∂
x
i
h
i
=
0
,
k
=
1
,
2
,
…
,
m
.
{\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
X
=
R
2
,
Y
=
R
{\displaystyle X=\mathbb {R} ^{2},Y=\mathbb {R} }
F
(
x
,
y
)
=
f
(
x
,
y
)
+
λ
G
(
x
,
y
)
{\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]
F
x
′
=
0
,
F
y
′
=
0
,
{\displaystyle F'_{x}=0,F'_{y}=0,}
λ
.
{\displaystyle \lambda .}
G
(
x
,
y
)
=
0.
{\displaystyle G(x,y)=0.}
{
D
(
f
,
G
)
D
(
x
,
y
)
=
0
G
(
x
,
y
)
=
0
,
{\displaystyle {\begin{cases}{\frac {D(f,G)}{D(x,y)}}=0\\[2pt]G(x,y)=0\end{cases}},}
gdzie
D
(
f
,
G
)
D
(
x
,
y
)
{\displaystyle {\tfrac {D(f,G)}{D(x,y)}}}
jakobian funkcji
f
{\displaystyle f}
G
.
{\displaystyle G.}
Przykład – ekstrema funkcji na okręgu [ edytuj | edytuj kod ] Wykresem funkcji
f
(
x
,
y
)
=
x
+
y
{\displaystyle f(x,y)=x+y}
płaszczyzna . W przestrzeni trójwymiarowej równanie
x
2
+
y
2
=
1
{\displaystyle x^{2}+y^{2}=1}
walca (którego podstawą jest leżący na płaszczyźnie
x
y
{\displaystyle 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
{\displaystyle f(x,y)=x+y}
na okręgu jednostkowym, tj. przy warunku
x
2
+
y
2
=
1.
{\displaystyle x^{2}+y^{2}=1.}
Zatem funkcja
G
{\displaystyle G}
G
(
x
,
y
)
=
x
2
+
y
2
−
1
,
{\displaystyle G(x,y)=x^{2}+y^{2}-1,}
a funkcja
F
{\displaystyle F}
F
(
x
,
y
,
λ
)
=
f
(
x
,
y
)
+
λ
G
(
x
,
y
)
=
x
+
y
+
λ
(
x
2
+
y
2
−
1
)
.
{\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ń
{
F
x
′
(
x
,
y
)
=
1
+
2
λ
x
=
0
F
y
′
(
x
,
y
)
=
1
+
2
λ
y
=
0
G
(
x
,
y
)
=
x
2
+
y
2
−
1
=
0
.
{\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
x
≠
0
y
≠
0
{\displaystyle x\neq 0\,\,y\neq 0}
λ
=
−
1
2
x
,
{\displaystyle \lambda =-{\tfrac {1}{2x}},}
λ
=
−
1
2
y
{\displaystyle \lambda =-{\tfrac {1}{2y}}}
x
=
y
{\displaystyle x=y}
2
x
2
=
1
,
{\displaystyle 2x^{2}=1,}
x
=
±
2
2
.
{\displaystyle x=\pm {\tfrac {\sqrt {2}}{2}}.}
f
{\displaystyle f}
(
−
2
2
,
−
2
2
)
,
(
2
2
,
2
2
)
.
{\displaystyle \left(-{\tfrac {\sqrt {2}}{2}},-{\tfrac {\sqrt {2}}{2}}\right),\left({\tfrac {\sqrt {2}}{2}},{\tfrac {\sqrt {2}}{2}}\right).}
zbiorem domkniętym i ograniczonym (czyli zwartym [4] twierdzenia Weierstrassa , funkcja
f
{\displaystyle f}
minimum warunkowe:
f
(
−
2
2
,
−
2
2
)
=
−
2
,
{\displaystyle f\left(-{\tfrac {\sqrt {2}}{2}},-{\tfrac {\sqrt {2}}{2}}\right)=-{\sqrt {2}},}
maksimum warunkowe:
f
(
2
2
,
2
2
)
=
2
.
{\displaystyle f\left({\tfrac {\sqrt {2}}{2}},{\tfrac {\sqrt {2}}{2}}\right)={\sqrt {2}}.}
Warto zauważyć, że funkcja
f
,
{\displaystyle f,}
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
,
…
,
p
n
{\displaystyle p_{1},\dots ,p_{n}}
f
(
p
1
,
p
2
,
…
,
p
n
)
=
−
∑
k
=
1
n
p
k
log
2
p
k
.
{\displaystyle 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
,
…
,
p
n
{\displaystyle p_{1},\dots ,p_{n}}
G
{\displaystyle G}
G
(
p
1
,
p
2
,
…
,
p
n
)
=
∑
k
=
1
n
p
k
−
1.
{\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
n
{\displaystyle n}
∂
∂
p
k
(
f
(
p
1
,
p
2
,
…
,
p
n
)
+
λ
(
G
(
p
1
,
p
2
,
…
,
p
n
)
)
)
=
0
,
1
⩽
k
⩽
n
,
{\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
∂
∂
p
k
(
−
∑
k
=
1
n
p
k
log
2
p
k
+
λ
(
∑
k
=
1
n
p
k
−
1
)
)
=
0
,
1
⩽
k
⩽
n
.
{\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
p
k
,
{\displaystyle p_{k},}
−
(
1
ln
2
+
log
2
p
k
)
+
λ
=
0
,
1
⩽
k
⩽
n
.
{\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.
p
1
=
…
=
p
n
,
{\displaystyle p_{1}=\ldots =p_{n},}
1
⩽
k
⩽
n
:
{\displaystyle 1\leqslant k\leqslant n{:}}
p
k
=
1
n
.
{\displaystyle p_{k}={\frac {1}{n}}.}
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]
![{\displaystyle {\begin{cases}f'(x)=\Lambda \circ G'(x)\\[2pt]G(x)=0\end{cases}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b9b4c75c6e87b8fcbe419b4fc6d5a691944807)
![{\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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e3673892f04f2b97a88f5407e4b3e50ccffd394)
![{\displaystyle {\begin{cases}{\frac {D(f,G)}{D(x,y)}}=0\\[2pt]G(x,y)=0\end{cases}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1367514597b919bef644ce9d47e627c96ee40eb)
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/732f24d6d7045eb9ebbb5a8e743f868ad7c26b5e)
