Metoda Lagrangeových multiplikátorů

Sedlový bod Lagrangeovy funkce. Metoda Lagrangeových multiplikátorů slouží k nalezení vázaných extrémů funkce, tedy jejích minim nebo maxim při platnosti omezujících podmínek.

Vázané extrémy diferencovatelné reálné funkce f\left( x_1, \ldots, x_n \right) za předpokladu platnosti diferencovatelných omezujících podmínek g_k\left( x_1, \ldots , x_n \right) = 0, kde k \in \{1, \ldots ,m\}, lze najít pomocí tzv. Lagrangeovy funkce:

:\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)},

kde proměnné \lambda _1,\ldots , \lambda _m jsou tzv. Lagrangeovy multiplikátory.

Za určitých podmínek, známých jako Kuhnovy-Tuckerovy, leží lokální vázaný extrém funkce f v tzv. sedlovému bodě Lagrangeovy funkce. +more Sedlové body najdeme položením parciálních derivací Lagrangeovy funkce rovných nule.

Metodu Lagrangeových multiplikátorů uveřejnil Joseph-Louis Lagrange počátkem 19. století.

Omezení ve tvaru rovností

Formulujme optimalizační úlohu následovně:

: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}

kde {\overrightarrow{x_{0}}} je optimum, \mathrm{\Omega} vymezuje oblast přípustných řešení ve tvaru rovností resp. nerovností a f představuje optimalizovanou funkci.

Uvažujme uvedenou optimalizační úlohu s následující oblastí přípustných řešení ve tvaru rovností: :\overrightarrow{g}:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}\ \ \ \ \ \mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{g}(\overrightarrow{x}) = \overrightarrow{0}\}\ \ \ \ \ m

kde f a g_{j} jsou spojitě diferencovatelné funkce a dále zaveďme tzv. Lagrangeovu funkci:

:\mathcal{L}:\mathbb{R}^{n + m}\mathbb{\rightarrow R}\ \ \ \ \ \mathcal{L}(\overrightarrow{z}) = f(\overrightarrow{x}) + \overrightarrow{\lambda}.\overrightarrow{g}(\overrightarrow{x})\ \ \ \ \ \overrightarrow{z} = \lbrack \overrightarrow{x},\overrightarrow{\lambda} \rbrack\ \ \ \ \ (2)

kde složky vektoru \overrightarrow{\lambda} jsou tzv. Lagrangeovy multiplikátory, pak za předpokladu lineární nezávislosti vektorů \nabla g_{1}(\overrightarrow{x}),\ldots,\nabla g_{m}(\overrightarrow{x}) je nutná podmínka existence lokálního extrému funkce (2) v bodě {\overrightarrow{z_{0}}} ve tvaru \nabla \mathcal{L}({\overrightarrow{z_{0}}}) = \overrightarrow{0}, tj. +more:.

:\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}

:\frac{\partial \mathcal{L}}{\partial \lambda_{j}} = g_{j} = 0

kde i \in \{1, - ,n\},\ \ \ j \in \{1, - ,m\}.

Omezení ve tvaru nerovností (Kuhn-Tucker)

Omezení ve tvaru nerovností optimalizačního problému pro vnitřní resp. +more hraniční bod. 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é \overrightarrow{y}:.

:\mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{g}(\overrightarrow{x}) + \overrightarrow{y} = \overrightarrow{0}\}\ \ \ \ \ (3)

:\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)

spolu s ekvivalentními nutnými podmínkami existence lokálního extrému funkce v bodě {\overrightarrow{z_{0}}}:

:\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}

:\frac{\partial \mathcal{L}}{\partial y_{j}} = \lambda_{j} = 0

:\frac{\partial \mathcal{L}}{\partial\lambda_{j}} = g_{j} + y_{j} = 0.

Uvažujme nyní obecně omezení úlohy pouze ve tvaru \mathrm{\Omega} = \{\overrightarrow{x} \in \mathbb{R}^{n} | \overrightarrow{x} \geq \overrightarrow{0}\}, pak pro optimální vnitřní resp. hraniční bod z \Omega platí:

:\forall i\ \ \ x_{0i} > 0 \Rightarrow \frac{\partial f}{\partial x_{0i}} = 0\ \ \ \ \ resp. \ \ \ \ \ \exists j\ \ \ x_{0j} = 0 \Rightarrow \frac{\partial f}{\partial x_{0j}} \geq 0

kde i,j \in \{ 1, - ,n\}, takže zřejmě pro libovolný optimální bod z \Omega platí:

:\forall i\ \ \ x_{0i}\ \frac{\partial f}{\partial x_{0i}} = 0\ \ \ \ \ (5)

tj. pak můžeme nutnou podmínku existence lokálního extrému funkce v bodě {\overrightarrow{x_{0}}} zapsat pomocí (5) ve tvaru:

:\nabla f({\overrightarrow{x_{0}}}) \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{x_{0}}}\cdot \nabla f({\overrightarrow{x_{0}}}) = 0\ \ \ \ \ ( 6).

Vzhledem k výše uvedenému dostaneme pro \overrightarrow{x} \geq \overrightarrow{0} a \overrightarrow{y} \geq \overrightarrow{0} následující soustavu nutných podmínek existence lokálního extrému funkce (4) analogicky s (6) v bodě {\overrightarrow{z_{0}}}:

:\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{x}}_{0}\cdot\frac{\partial \mathcal{L}}{\partial\overrightarrow{x}} = 0

:\frac{\partial \mathcal{L}}{\partial\overrightarrow{y}} \geq \overrightarrow{0}\ \ \ \ \ {\overrightarrow{y}}_{0}\cdot\frac{\partial \mathcal{L}}{\partial\overrightarrow{y}} = 0

:\frac{\partial \mathcal{L}}{\partial\overrightarrow{ \lambda}} = \overrightarrow{g}({\overrightarrow{x_{0}}}) + {\overrightarrow{y_{0}}} = \overrightarrow{0}

a úpravou uvedených podmínek můžeme vypuštěním pomocné proměnné \overrightarrow{y} vyjádřit nutné podmínky existence lokálního extrému funkce (2) v bodě {\overrightarrow{z_{0}}} na oblasti vymezené nerovnostmi v tzv. Karushově-Kuhnově-Tuckerově kompaktním symetrickém tvaru:

:\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)

:\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)

a bod {\overrightarrow{z_{0}}} je tzv. sedlovým bodem funkce (2), tj. +more Lagrangeova funkce v něm nabývá svého minima resp. maxima vzhledem k proměnným \overrightarrow{x} resp. \overrightarrow{\lambda} a dle (8) platí \mathcal{L}({\overrightarrow{z_{0}}}) = f({\overrightarrow{x _{0}}}), takže {\overrightarrow{x_{0}}} je zřejmě hledané optimum funkce f na oblasti vymezené omezujícími podmínkami ve tvaru nerovností. Sedlový bod funkce (2) pak získáme řešením soustavy n+m nelineárních rovnic o n+m neznámých určené skalárními součiny (7) a (8).

Příklad

+more1'>Extrémní hodnoty lineární funkce na kružnici Najděme maximum lineární funkce f(x,y)=x+y vázané na jednotkovou kružnici x^2+y^2=1.

Vazba je

:g(x,y)=x^2+y^2-1,

takže Lagrangeova funkce je

:\begin{align} \mathcal{L}(x, y, \lambda) &= f(x,y) + \lambda \cdot g(x,y) \\ &= x+y + \lambda (x^2 + y^2 - 1). \end{align}

Derivací Lagrangeovy funkce podle jednotlivých proměnných získáme gradient:

:\begin{align} \nabla_{x,y,\lambda} \mathcal{L}(x , y, \lambda) &= \left ( \frac{\partial \mathcal{L}}{\partial x}, \frac{\partial \mathcal{L}}{\partial y}, \frac{\partial \mathcal{L}}{\partial \lambda} \right ) \\ &= \left ( 1 + 2 \lambda x, 1 + 2 \lambda y, x^2 + y^2 -1 \right ) \end{align}

a jeho položením rovného nule dostaneme soustavu tří rovnic pro tři neznámé proměnné:

:\nabla_{x,y,\lambda} \mathcal{L}(x , y, \lambda)=0 \quad \Leftrightarrow \quad \begin{cases} 1 + 2 \lambda x = 0 \\ 1 + 2 \lambda y = 0 \\ x^2 + y^2 -1 = 0. \end{cases}

Poslední rovnice je vazba, z prvních dvou rovnic dostaneme

:x= y = - \frac{1}{2\lambda}, \qquad \lambda \neq 0.

Dosazením do poslední rovnice máme

:\frac{1}{4\lambda^2}+\frac{1}{4\lambda^2} - 1=0,

takže

:\lambda = \pm \frac{1}{\sqrt{2}},

což po dopočítání x a y vede k závěru, že řešení (stacionární body \mathcal{L}) jsou

:\left(\tfrac{\sqrt{2}}{2},\tfrac{\sqrt{2}}{2}, -\tfrac{1}{\sqrt{2}}\right), \qquad \left(-\tfrac{\sqrt{2}}{2}, -\tfrac{\sqrt{2}}{2}, \tfrac{1}{\sqrt{2}}\right).

Vypočítáme hodnoty v těchto bodech (zajímají nás jen první dvě souřadnice stacionárních bodů, třetí souřadnice odpovídá multiplikátoru, který v tuto chvíli už nepotřebujeme):

:f\left(\tfrac{\sqrt{2}}{2},\tfrac{\sqrt{2}}{2}\right)=\sqrt{2}, \qquad f\left(-\tfrac{\sqrt{2}}{2}, -\tfrac{\sqrt{2}}{2}\right)=-\sqrt{2}.

Vázané maximum tedy je \sqrt{2} a vázané minimum -\sqrt{2}.

Geometrický význam

+more5'>Funkce dvou proměnných f(x, y) je znázorněna fialovou plochou. Úlohou je najít maximální hodnotu této funkce ležící na červené vazebné křivce g(x, y) = 0 (vázaný extrém). Modré ovály jsou „vrstevnice“ funkce f, tedy geometrická místa s konstantní hodnotou funkce; menší modrý ovál je vrstevnice, na které leží vázaný extrém. tečnu Ve dvourozměrném případě na obrázcích je naznačena funkce f a její vrstevnice f(x,y)=0, jakož i křivka g(x,y)=0 odpovídající vazbě. Hledáme nejvyšší hodnotu f, která se nachází na bodech této červeně vyznačené křivky (tj. vázaný extrém).

Vázaný extrém se může vyskytnout pouze na vrstevnici, kterou křivka vazby neprotíná. Jinak totiž se na jedné straně od takové vrstevnice nacházejí hodnoty vyšší a na druhé straně nižší než f(x,y) a proto zde nemůže nastat extrém; postupem po křivce vazby se totiž hned v sousedství daného bodu dostaneme na hodnoty vyšší nebo nižší než v tomto bodě.

Pokud se vrstevnice a křivka vazby neprotínají, musejí se dotýkat (být si lokálně tečnami). Stačí tedy analyticky vyjádřit, že se dvě křivky dotýkají, a máme nutnou podmínku vázaného extrému. +more K tomu účelu si uvědomme, že „lokální směr“ přímky nebo plochy určuje gradient - vektor, mířící ve směru největšího zakřivení a tedy kolmý na tečnu. Na nižším obrázku jsou gradienty naznačeny jako malé šipky vycházející z křivek.

Protože tečny jsou stejné, musejí být až na měřítko shodné i gradienty - musejí mířit stejným (anebo přesně opačným) směrem. Existuje tedy nenulová konstanta \lambda tak, že v bodě dotyku [x_0,y_0] platí

: \nabla f=\lambda \cdot \nabla g

neboli

: \nabla f - \lambda \cdot \nabla g = 0,

kde \nabla f je gradient f v tomto bodě a \nabla g je gradient g tamtéž. Souřadnice gradientů dostaneme jako parciální derivace příslušných funkcí podle jednotlivých souřadnic, což umožní uvedenou vektorovou rovnici rozepsat po souřadnicích:

: \left\{\begin{array}{llcc} \dfrac{\partial f}{\partial x}\Big|_{(x_0,\;y_0)} & -\lambda \cdot \dfrac{\partial g}{\partial x}\Big|_{(x_0,\;y_0)} & = & 0\\ \dfrac{\partial f}{\partial y}\Big|_{(x_0,\;y_0)} & -\lambda \cdot \dfrac{\partial g}{\partial y}\Big|_{(x_0,\;y_0)} & = & 0.\\ \end{array}\right.

Pokud k těmto dvěma rovnicím připojíme ještě třetí, vazební rovnici g(x,y)=0, dostaneme přesně totéž, co bychom získali parciálním derivováním příslušné Lagrangeovy funkce

:\begin{align} \mathcal{L}(x, y, \lambda) &= f(x,y) + \lambda \cdot g(x,y) \\ \end{align}

podle všech tří jejích argumentů a položením jednotlivých derivací rovných nule.

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

Externí odkazy

Kategorie:Optimalizace (matematika)