Wikipedie

Metoda Lagrangeových multiplikátorů: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
JAnDbot (diskuse | příspěvky)
Roboti
1 716 378 editací
m {{Commonscat}}; kosmetické úpravy
rekonstrukce stránky
Řádek 1:
'''Metoda Lagrangeových multiplikátorů''' byla představena [[Joseph-Louis Lagrange|Josephem-Louis Lagrangem]] počátkem 19. století. Jedná se o metodu nalezení vázaných extrémů diferencovatelné funkce za předpokladu platnosti diferencovatelných [[omezující podmínky|omezujících podmínek]]. Hledáme vázané extrémy funkce <math>f\left( x_1, \ldots, x_n \right)</math> za předpokladu platnosti omezujících podmínek <math>g_k\left( x_1, \ldots , x_n \right) = 0</math> kde <math>k \in \{1, - ,m\}</math> vytvořením tzv. ''Lagrangeovy funkce'':
[[Soubor:Joseph Louis Lagrange. Line engraving by Locatelli. Wellcome V0003310.jpg|náhled|Lagrange]]
'''Metoda Lagrangeových multiplikátorů''' neboli '''Lagrangeova metoda neurčitých koeficientů''' je metoda, jak nalézt extrémy diferencovatelné funkce za předpokladu platnosti diferencovatelných [[omezující podmínky|omezujících podmínek]]. Uveřejnil ji [[Joseph-Louis Lagrange]] počátkem 19. století.
 
:<math>\mathcal{L}\left( x_1,\ldots , x_n, \lambda_1, \ldots, \lambda _m \right) = f\left( x_1, \ldots, x_n \right) + \sum\limits_{k=1}^m {\lambda_k g_k\left( x_1, \ldots , x_n \right)}</math>
Jestliže hledáme extrémy funkce <math>f\left( x_1, \ldots, x_n \right)</math> za předpokladu platnosti ''m'' vazeb (omezujících podmínek) ve tvaru
 
:kde <math>g_k\left(lambda x_1_1, \ldots , x_n \right)lambda = 0,_m</math> jsou tzv. ''Lagrangeovy multiplikátory''.
 
== Omezení ve tvaru rovností ==
kde ''n'' a ''k'' jsou přirozená čísla a ''k'' nabývá hodnot mezi 1 a ''m'', tak metoda Lagrangeových multiplikátorů začíná vytvořením ''Lagrangeovy funkce'' <math>\mathcal{L}</math>, závislé na ''n'' + ''m'' proměnných:
Formulujme optimalizační úlohu následovně:
 
:<math>f:\mathbb{R}^{n}\mathbb{\rightarrow R}\ \ \ \ \ f({\overrightarrow{x_{0}}}) = \min_{\overrightarrow{x} \in \mathrm{\Omega}}{f(\overrightarrow{x})}\ \ \ \ \ \mathrm{\Omega} \subset \mathbb{R}^{n}</math>
:<math>\mathcal{L}\left( x_1,\ldots , x_n, \lambda_1, \ldots, \lambda _m \right) = f\left( x_1, \ldots, x_n \right) + \sum\limits_{k=1}^m {\lambda_k g_k\left( x_1, \ldots , x_n \right)}.</math>
 
kde <math>{\overrightarrow{x_{0}}}</math> je optimum, <math>\mathrm{\Omega}</math> vymezuje oblast přípustných řešení ve tvaru rovností resp. nerovností a <math>f</math> představuje optimalizovanou funkci.
Kromě původních proměnných <math>x_1,\ldots , x_n</math> tedy zavádíme další neznámé <math>\lambda _1,\ldots , \lambda _m</math>, zvané ''Lagrangeovy multiplikátory''. Nyní platí, že pokud se hledaný vázaný extrém nalézá v bodě, kde jsou všechny zkoumané funkce diferencovatelné, pak tento bod splňuje kromě ''m'' vazebných rovnic uvedených výše také ''n'' rovnic tvaru
 
Uvažujme uvedenou optimalizační úlohu s následující oblastí přípustných řešení ve tvaru rovností:
:<math>\frac{\partial \mathcal{L}}{\partial x_i} = 0,</math>
:<math>\overrightarrow{g}:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}\ \ \ \ \ \mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{g}(\overrightarrow{x}) = \overrightarrow{0}\}\ \ \ \ \ m < n\ \ \ \ \ (1)</math>
 
kde <math>f</math> a <math>g_{j}</math> jsou spojitě diferencovatelné funkce a dále zaveďme tzv. ''Lagrangeovu'' funkci:
což je totéž jako
 
:<math>\mathcal{L}:\mathbb{R}^{n + m}\mathbb{\rightarrow R}\ \ \ \ \ \mathcal{L}(\overrightarrow{z}) = f(\overrightarrow{x}) +
:<math>\frac{\partial f}{\partial x_i} = \sum_{k=1}^m \lambda_k \frac{\partial g_k}{\partial x_i}.</math>
\overrightarrow{\lambda}.\overrightarrow{g}(\overrightarrow{x})\ \ \ \ \ \overrightarrow{z} = \lbrack \overrightarrow{x},\overrightarrow{\lambda} \rbrack\ \ \ \ \ (2)</math>
 
kde složky vektoru <math>\overrightarrow{\lambda}</math> jsou tzv. Lagrangeovy multiplikátory, pak za předpokladu lineární nezávislosti vektorů
Tím získáme soustavu ''n'' + ''m'' rovnic pro ''n'' + ''m'' proměnných, jejímž řešením najdeme potenciální extrémy. Pak je potřeba vyšetřit, zda se jedná o maxima, minima nebo sedlové body. V případě, že zúčastněné funkce vykazují nediferencovatelné body, je potřeba zvlášť vyšetřit i tyto, neboť i zde se mohou hledané extrémy nacházet.
<math>\nabla g_{1}(\overrightarrow{x}),\ldots,\nabla g_{m}(\overrightarrow{x})</math> je nutná podmínka existence lokálního extrému funkce (2) v bodě <math>{\overrightarrow{z_{0}}}</math> ve tvaru <math>\nabla \mathcal{L}({\overrightarrow{z_{0}}}) = \overrightarrow{0}</math>, tj.:
 
:<math>\frac{\partial \mathcal{L}}{\partial x_{i}} = \frac{\partial f}{\partial x_{i}} + \sum_{j}^{}{\lambda_{j}\frac{\partial g_{j}}{\partial x_{i}} = 0}</math>
Poněvadž ''m'' vazebných podmínek lze získat tím, že Lagrangeovu funkci parciálně zderivujeme podle multiplikátorů a derivace položíme rovny nule, lze souhrnně říci, že [[Nutná podmínka|nutnou podmínkou]] existence vázaného extrému za podmínek diferencovatelnosti v daném bodě je, aby [[Gradient (matematika)|gradient]] Lagrangeovy funkce v tomto bodě vymizel, což lze [[vektor]]ově zapsat jako:
 
:<math>\nabla_frac{\mathbf{x},partial \boldsymbolmathcal{\lambdaL}}{\partial \mathcallambda_{Lj}} (\mathbf= g_{xj}, \boldsymbol{\lambda})= 0,</math>
 
kde <math>i \in \{1, - ,n\},\ \ \ j \in \{1, - ,m\}</math>.
což znamená, že Lagrangeovu funkci je potřeba postupně zderivovat podle všech jejích ''n'' + ''m'' proměnných, derivace položit rovny nule a soustavu vyřešit. Řešení udávají souřadnice bodů, v nichž může (ale nemusí) existovat hledaný vázaný extrém.
 
== Omezení ve tvaru nerovností (Kuhn-Tucker) ==
Zaměníme-li v oblasti přípustných řešení (1) rovnost za nerovnost, tj. přejdeme-li od omezení ve tvaru rovností k omezení ve tvaru nerovností,
můžeme se vrátit zpět k omezení ve tvaru rovností ekvivalentním vyjádřením následujících omezení a Lagrangeovy funkce zavedením pomocné
proměnné <math>\overrightarrow{y}</math>:
 
:<math>\mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{g}(\overrightarrow{x}) + \overrightarrow{y} = \overrightarrow{0}\}\ \ \ \ \ (3)</math>
 
:<math>\mathcal{L}(\overrightarrow{z}) = f(\overrightarrow{x}) + \overrightarrow{\lambda}.(\overrightarrow{g}(\overrightarrow{x})) + \overrightarrow{y})\ \ \ \ \
\overrightarrow{z} = \lbrack \overrightarrow{x},\overrightarrow{y},\overrightarrow{\lambda} \rbrack\ \ \ \ \ (4)</math>
 
spolu s ekvivalentními nutnými podmínkami existence lokálního extrému funkce v bodě <math>{\overrightarrow{z_{0}}}</math>:
 
:<math>\frac{\partial \mathcal{L}}{\partial x_{i}} = \frac{\partial f}{\partial x_{i}} + \sum_{j}^{}{\lambda_{j}\frac{\partial g_{j}}{\partial x_{i}} = 0}</math>
 
:<math>\frac{\partial \mathcal{L}}{\partial y_{j}} = \lambda_{j} = 0</math>
 
:<math>\frac{\partial \mathcal{L}}{\partial\lambda_{j}} = g_{j} + y_{j} = 0</math>
 
Uvažujme nyní obecně omezení úlohy pouze ve tvaru <math>\mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{x} \geq \overrightarrow{0}\}</math>, pak pro optimální vnitřní resp. hraniční bod z <math>\Omega</math> platí:
 
:<math>\forall i\ \ \ x_{0i} > 0 \Rightarrow \frac{\partial f}{\partial x_{0i}} = 0\ \ \ \ \ </math> resp. <math>\ \ \ \ \ \exists j\ \ \ x_{0j} = 0 \Rightarrow \frac{\partial f}{\partial x_{0j}} \geq 0</math>
 
kde <math>i,j \in \{ 1, - ,n\}</math>, takže zřejmě pro libovolný optimální bod z <math>\Omega</math> platí:
 
:<math>\forall i\ \ \ x_{0i}\ \frac{\partial f}{\partial x_{0i}} = 0\ \ \ \ \ (5)</math>
 
tj. pak můžeme nutnou podmínku existence lokálního extrému funkce v bodě <math>{\overrightarrow{x_{0}}}</math> zapsat pomocí (5) ve tvaru:
 
:<math>\nabla f({\overrightarrow{x_{0}}}) \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{x_{0}}}\cdot \nabla f({\overrightarrow{x_{0}}}) = 0\ \ \ \ \ ( 6)</math>
 
Vzhledem k výše uvedenému dostaneme pro <math>\overrightarrow{x} \geq \overrightarrow{0}</math> a <math>\overrightarrow{y} \geq \overrightarrow{0}</math> následující soustavu nutných podmínek existence lokálního extrému funkce (4) analogicky s (6) v bodě <math>{\overrightarrow{z_{0}}}</math>:
 
:<math>\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{x}}_{0}\cdot\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} = 0</math>
 
:<math>\frac{\partial \mathcal{L}}{\partial\overrightarrow{y}} \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{y}}_{0}\cdot\frac{\partial \mathcal{L}}{\partial\overrightarrow{y}} = 0</math>
 
:<math>\frac{\partial \mathcal{L}}{\partial\overrightarrow{ \lambda}} = \overrightarrow{g}({\overrightarrow{x_{0}}}) + {\overrightarrow{y_{0}}} = \overrightarrow{0}</math>
 
a úpravou uvedených podmínek můžeme vypuštěním pomocné proměnné <math>\overrightarrow{y}</math> vyjádřit nutné podmínky existence lokálního
extrému funkce (2) v bodě <math>{\overrightarrow{z_{0}}}</math> na oblasti vymezené nerovnostmi v tzv. ''Karush-Kuhn-Tuckerově'' kompaktním symetrickém
tvaru:
<ref>
{{Citace kvalifikační práce
| příjmení = Karush
| jméno = William
| titul = Minima of Functions of Several Variables with Inequalities as Side Constraints (Minima funkcí více proměnných s nerovnostmi jako omezujícími podmínkami)
| typ práce = Disertační práce
| instituce = Dept of Mathematics, Univ. of Chicago, Chicago, Illinois
| rok = 1939
}}
</ref><ref>
{{Citace sborníku
| příjmení = Kuhn
| jméno = Harold W.
| příjmení2 = Tucker
| jméno2 = Albert W.
| sborník = Proceedings of Symposium 2. Berkeley
| strany = 481–492
| kapitola = Nelineární programování
| vydavatel = University of California Press
| rok vydání = 1951
| místo = Berkeley
}}</ref>
 
:<math>\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} \geq \overrightarrow{0}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\overrightarrow{x_{0}}} \geq \overrightarrow{0}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\overrightarrow{x_{0}}}\cdot\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} = 0\ \ \ \ \ (7)</math>
 
:<math>\overrightarrow{g}({\overrightarrow{x_{0}}}) \leq \overrightarrow{0}\ \ \ \ \ \ \ \ \ \ \ \ {\overrightarrow{\lambda_{0}}} \geq \overrightarrow{0}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\overrightarrow{\lambda_{0}}}\cdot\overrightarrow{g}({\overrightarrow{x_{0}}}) = 0\ \ \ \ \ (8)</math>
 
a bod <math>{\overrightarrow{z_{0}}}</math> je tzv. ''sedlovým'' bodem funkce (2), tj. Lagrangeova funkce v něm nabývá svého minima resp. maxima vzhledem k proměnným <math>\overrightarrow{x}</math> resp. <math>\overrightarrow{\lambda}</math> a dle (8) platí <math>\mathcal{L}({\overrightarrow{z_{0}}}) = f({\overrightarrow{x _{0}}})</math>, takže <math>{\overrightarrow{x_{0}}}</math> je zřejmě hledané optimum kriteriální funkce <math>f</math> na oblasti vymezené omezujícími podmínkami ve tvaru nerovností. Sedlový bod funkce (2) pak získáme řešením soustavy <math>n+m</math> nelineárních rovnic o <math>n+m</math> neznámých určené skalárními součiny (7) a (8).
 
== Příklad ==
[[Soubor:Lagrange very simple.svg|náhled|vpravo|upright=1.1|Extrémní hodnoty lineární fukce na kružnici]]
 
Najděme maximum [[lineární funkce]] <math>f(x,y)=x+y</math> vázané na jednotkovou kružnici <math>x^2+y^2=1</math>.
 
Řádek 108 ⟶ 180:
 
Tato úvaha není důkazem v přísném smyslu, protože se opírá o geometrickou intuici a neřeší různé zvláštní případy (zejména co se stane, když některý z gradientů vymizí – je roven nulovému vektoru). Lze ji však snadno zobecnit na více proměnných a vazeb, a odůvodnit tak obecnou Lagrangeovu metodu.
 
== Reference ==
<references />
 
== Externí odkazy ==
Citováno z „https://cs.wikipedia.org/wiki/Metoda_Lagrangeových_multiplikátorů“