# Numerické metody v Rⁿ <div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0"> ```math \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}} \letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\addLabel}{2}{\cssId{#1-#2}{\text{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}} \letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addLabel{sec}{#1}} \letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}} \letThereBe{\eqRefAt}{2}{\href{#2\#eq-#1}{(\text{#1})}} \letThereBe{\secRefAt}{2}{\href{#2\#sec-#1}{(\text{#1})}} \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}} \letThereBe{\rcases}{1}{\left.\begin{align}#1\end{align}\right\}} \letThereBe{\rcasesAt}{2}{\left.\begin{alignat}{#1}#2\end{alignat}\right\}} \letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}} \letThereBe{\lcasesAt}{2}{\left\{\begin{alignat}{#1}#2\end{alignat}\right.} \letThereBe{\scal}{2}{\langle #1, #2 \rangle} \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \LetThereBe{\dist}{\rho} \LetThereBe{\and}{\&}\letThereBe{\brackets}{1}{\left\{ #1 \right\}} \letThereBe{\parc}{2}{\frac {\partial #1}{\partial #2}} \letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}} \letThereBe{\bm}{1}{\boldsymbol{#1}} \letThereBe{\mcal}{1}{\mathcal{#1}} \letThereBe{\vv}{1}{\mathbf{#1}}\letThereBe{\vvp}{1}{\pmb{#1}} \LetThereBe{\ve}{\varepsilon} \LetThereBe{\l}{\lambda} \LetThereBe{\th}{\vartheta} \LetThereBe{\a}{\alpha} \LetThereBe{\vf}{\varphi} \letThereBe{\conv}{1}{\mathrm{conv}\, #1} \letThereBe{\cone}{1}{\mathrm{cone}\, #1} \letThereBe{\aff}{1}{\mathrm{aff}\, #1} \letThereBe{\lin}{1}{\mathrm{Lin}\, #1} \letThereBe{\span}{1}{\mathrm{span}\, #1} \LetThereBe{\O}{\mathcal O} \letThereBe{\ri}{1}{\mathrm{ri}\, #1} \letThereBe{\rd}{1}{\mathrm{r}\partial\, #1} \letThereBe{\interior}{1}{\mathrm{int}\, #1} \LetThereBe{\proj}{\Pi} \letThereBe{\epi}{1}{\mathrm{epi}\, #1} \letThereBe{\grad}{1}{\mathrm{grad}\, #1} \letThereBe{\gradT}{1}{\mathrm{grad}^T #1} \letThereBe{\gradx}{1}{\mathrm{grad}_x #1} \letThereBe{\hess}{1}{\nabla^2\, #1} \letThereBe{\hessx}{1}{\nabla^2_x #1} \letThereBe{\jacobx}{1}{D_x #1} \letThereBe{\jacob}{1}{D #1} \letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1} \letThereBe{\iter}{1}{^{[#1]}} \LetThereBe{\str}{^*} \LetThereBe{\spv}{\mcal V} \LetThereBe{\civ}{\mcal U} \LetThereBe{\knvxProg}{\eqRefAt{4.1}{./nutne-a-postacujici-podminky-optimality} \, \and \, \eqRefAt{4.2}{./nutne-a-postacujici-podminky-optimality}} \letThereBe{\set}{1}{\left\{ #1 \right\}} ``` </div> Budeme se věnovat úlohám (přesněji numerickým metodám jejich řešení) typu ```math f(x) \to \min, \quad x \in \R^n, \eqT{3.2.1} ``` kde $f:\R^n \to \R$ je *(jednou/dvakrát/třikrát)* **spojitě diferencovatelná** funkce. Obecně jsou metody numerické optimalizace založeny na **minimalizační posloupnosti** $\brackets{x^{[k]}}$ definované jako ```math x^{[k+1]} = x^{[k]} + \a_k h_k, ``` kde $\a_k \in \R$ se nazývá **délka** $k$**-tého kroku** a vektor $h_k \in \R^n$ je **směr** $k$**-tého vektoru**. > Budeme uvažovat tzv. **přesnou minimalizaci**, kdy dílčí minimalizace řešíme přesně (nikoliv numerickými metodami) > Všechny následující metody jsou **spádové** ### Metoda největšího spádu U této metody volíme ```math h_k = - \grad f(x^{[k]}), ``` přičemž délku kroku volíme **přesným řešením** úlohy ```math f(x^{[k+1]}) = f(x^{[k]} - \a_k \grad f(x^{[k]})) = \min_{\a \geq 0} f(x^{[k]} - \a \cdot \grad f(x^{[k]})) ``` Dále bude platit, že vektory určené body $x^{[k+1]}, x^{[k]}$ a $x^{[k+2]}, x^{[k+1]}$ jsou na sebe **ortogonální**. Z tohoto dostáváme, že pro daný směr hledáme **nejblížší** vrstevnici, která bude **tečná** k tomuto vektoru. Tato metoda je **prvního řádu** (stačí nám pouze gradient). > V některých případech dochází k tzv. "*cik-cak*" efektu (klikatěni), kdy se minimalizující posloupnost dostává k optimu velmi pomalu. Toto se děje například u **Rosenbrockovy (banánové) funkce** (jedna z *testovacích funkcí*) #### Kvadratické funkce Nechť $f$ je kvadratická funkce tvaru ```math f(x) = \frac 1 2 \scal {Qx} x - x^T b \eqT{3.2.2}, ``` kde $Q = Q^T > 0$ je **symetrická** $n \times n$ matice a $b \in \R^n$. Taková funkce $f$ je **ostře** (i *silně*) konvexní. Z pozitivní definitnosti $Q$ dostáváme, že vlastní čísla matice $Q$ jsou **kladné** a můžeme je uspořádat následovně ```math 0 < \l_1 \leq \l_2 \leq \dots \leq \l_n ``` Díky tomu můžeme úlohu $\eqRef{3.2.1}$ vyřešit "přímo" jako $x^*= Q^{-1} b$, nicméně počítání inverze může být **velice náročné** (výpočetně). V tomto případě je gradient $g$ funkce $f$ dán jako ```math g(x) := \grad f(x) = Qx - b, ``` tedy v jednotlivých iteracích dostáváme $g_k := Qx^{[k]} - b$ a $\a_k$ můžeme určit jako ```math \a_k = {g_k^T g_k \over g_k^T Q g_k} \in [1/\l_n, 1/\l_1] ``` Nyní se zaměříme na konvergenci metody, kterou můžeme zkoumat pomocí ```math E(x) := f(x) - f(x^*) = \frac 1 2 (x - x^*)^T Q (x - x^*) ``` ##### **Lemma** $\secT{3.2.1}$ (Konvergence metody největšího spádu) Platí ```math E(x^{[k+1]}) = \left(1 - {(g_k^T g_k)^2 \over (g_k^T Q g_k)(g_k^T Q^{-1} g_k)} \right) E(x^{[k]}) ``` --- Z Lemmatu $\secRef{3.2.1}$ okamžitě plyne, že pokud pro nějaké $k \in \N$ nastane ```math 1 = {(g_k^T g_k)^2 \over (g_k^T Q g_k)(g_k^T Q^{-1} g_k)}, \eqT{3.2.1-a} ``` tak v $k+1$ metoda největšího spádu nalezne řešení **přesně**. V opačném případě je metoda **nekonečně-kroková**. Rovnost $\eqRef{3.2.1-a}$ nastane v případě, že $g_k$ je **vlastním vektorem** matice $Q$, jinak řečeno gradient musí mířit **do středu** elipsy (*elipsoidu*). V případě, že $\l_1 = \dots = \l_n$ je konvergence **superlineární**. Naopak pokud $\l_1 = \dots = \l_{n-1} \neq \l_n$, tak může být konvergence **velice pomalá**. Ve skutečnosti ještě rychlost konvergence závisí na počátečním $x^{[0]}$ #### Nekvadratické funkce V případě nekvadratické funkce je metoda největšího spádu schopna nalézt **pouze stacionární body**. ##### **Lemma** $\secT{3.2.2iii}$ (Lokální konvergence) Nechť $f: \R^n \to \R$ je **spojitě diferencovatelná**. Jestliže bod $x^{[0]} \in \R^n$ je takový, že množina ```math \set{x \in \R^n \mid f(x) \leq f(x^{[0]})} ``` je **ohraničená**, pak posloupnost $\brackets{x^{[k]}}$ generovaná metodou největšího spádu konverguje k bodu $x^*$, kde $\grad f(x^*) = 0$. --- Pokud konverguje $\brackets{x^{[k]}}$ k bodu $x^*$ a funkce $f$ je **dvakrát** spojitě diferencovatelná **na okolí** $x^*$ a platí ```math aI \leq \hess f(x^*) \leq AI, ``` kde $a, A > 0$ (tedy $f$ je v okolí $x^*$ **silně konvexní**), pak metoda konverguje (**alespoň**) s rychlostí $\left(A - a \over A + a\right)^2$ > Tedy i pro nekvadratické funkce hraje velkou roli podmíněnost matice $\hess f(x^*)$ > Metoda největšího spádu se nejčastěji využívá v jiných metodách jako pomocné, když ony metody samotné v tu chvíli neposkytují dostatečné zlepšení Celkem můžeme *metodu největšího spádu* shrnout: - **globální** konvergence (pro nekvadratické metody za dalších předpokladů) - **pomalá** konvergence - mnohdy numericky ani nekonverguje - je základem pro další (lepší) metody ### Newtonova metoda Hlavní myšlenkou Newtonovy metody je, že v $(k+1)$-kroku, kde $k \in \N_0$, funkci $f$ aproximujeme **Taylorovým polynomem druhého řádu** se středem v bodě $x^{[k]}$ a jako $x^{[k+1]}$ volíme bod, ve kterém tento polynom nabývá svého minima. > Jinak řečeno místo **tečné nadroviny** k funkci konstruujeme **tečnou $n$-rozměrnou parabolu** Tedy místo funkce $f$ uvažujeme v $k$-tém kroku ```math T_k(x) := f(x^{[k]}) + \grad f(x^{[k]}) (x - x^{[k]}) + \frac 1 2 (x - x^{[k]})^T \hess f(x^{[k]}) (x - x^{[k]}) \approx f(x) ``` Jelikož hledáme řešení $T_k(x) \to \min$, tak výraz výše první zderivujme, z čehož dostaneme ```math \grad T_k(x) = \grad f(x^{[k]}) + \hess f(x^{[k]}) (x - x^{[k]}), ``` což v případě ***regulární*** matice $\hess f(x^{[k]})$ vede na ```math x^{[k+1]} = x^{[k]} - (\hess f(x^{[k]}))^{-1} \grad f(x^{[k]}) ``` > Pro $\hess f(x) > 0$ je funkce **konvexní** a nalezneme **minimum** Nicméně je důležité podotknout, že výpočet $(\hess f(x^{[k]}))^{-1}$ je **velmi výpočetně náročný**. Avšak v případě **kvadratické funkce** Newtonova metoda nalezne řešení **v jednom kroku**, tedy její rychlost konvergence je **superlineární** s řádem $\infty$. Regularita matice $\hess f(x^{[k]})$ je velmi důležitá pro konvergenci, viz následující věta. ##### **Věta** $\secT{3.2.5}$ Nechť $f \in C^3$ v okolí bodu $x^*\in \R^n$, který je **nedegenerovaným minimem**, tj. $\grad f(x^*) = 0$ a $\hess f(x^*) > 0$. Potom pro $x^{[0]} \in \R^n$ dostatečně blízko $x^*$ konverguje $\brackets{x^{[k]}}$ generovaná Newtonovou metodou k bodu $x^*$ **superlineárně** s řádem (*alespoň*) $p = 2$ (tj. *kvadraticky*). > Zde určit, co znamená "*dostatečně blízko* $x^*$" je obtížné Celkem můžeme *Newtonovu metodu* shrnout jako: - **velmi rychlá** konvergence - nutnost **dostatečně blízké počáteční aproximace** - velmi velká výpočetní náročnost při velkém $n$ (počtu dimenzí) ### Metoda sdružených gradientů Uvažujme situaci v úloze $\eqRef{3.2.1}$, kdy máme funkci ```math f(x) = \frac 1 2 x^T Q x - b^T x \eqT{MSG}, ``` kde $Q = Q^T \in \R^{n \times n}, Q > 0$ je symetrická matice a $b \in \R^n$. Pak nalezení úlohy $\eqRef{3.2.1} \, \and \, \eqRef{MSG}$ je ekvivalentní s řešením úlohy ```math Qx = b \eqT{MSGa}, ``` kterou umíme řešit například Gaussovou eliminací. Metoda sdružených gradientů je v případě $Q > 0$ přímou metodou, která dojde k řešení $\eqRef{MSGa}$ po $n$ krocích. Nicméně tento fakt lze brát také jako, že je to iterační metoda s velmi rychlou konvergencí v případě pozitivně definitní matice. ##### **Definice** $\secT{3.2.7}$ ($Q$-sdružené vektory) Nechť $Q = Q^T \in \R^{n \times n}$ je **pozitivně definitní**. Vektory $h_1, h_2 \in \R^n \setminus \set{0}$ se nazývají $Q$**-sdružené** (nebo také $Q$**-ortogonální**), jestliže ```math \scal {Qh_1} {h_2} = h_1^T Q h_2 = 0 ``` Systém vektorů $\set{h_0, \dots, h_{m-1}}$ v $\R^n \setminus \set{0}$ pro $m \in \set{2, \dots, n}$ se nazývá $Q$**-sdružený**, jestliže ```math \scal {Q h_i} {h_j} = 0 \text{ pro } i \neq j ``` ##### **Věta** $\secT{3.2.8}$ Nechť systém vektorů $\set{h_0, \dots, h_{m-1}}$ v $\R^n \setminus \set{0}$ s $m \in \set{2, \dots, n}$ je $Q$**-sdružený**. Potom jsou tyto vektory **lineárně nezávislé**. ##### **Věta** $\secT{3.2.9}$ Nechť $m \in \set{2, \dots, n}$ a mějme systém $Q$*-sdružených* vektorů $\set{h_0, \dots, h_{m-1}}$ v $\R^n$. Nechť $x \iter 0$ je **dáno** a body $x \iter 1, \dots, x \iter m$ jsou dány jako ```math x \iter {k+1} = x \iter k + \a_k h_k = x \iter 0 + \sum_{i = 0}^k \a_i h_i, \quad k \in \set{0, \dots, m-1}, \eqT{3.2.8} ``` kde $\a_k$ jsou volena tak, že $f(x \iter k + \a_k h_k) = \min_{\a \in \R} f(x \iter k + \a h_k)$ pro $k \in \set{0, \dots, m-1}$ (tj. jsou volena **přesnou minimalizací**). Pak pro kvadratickou funkci $f$ definovanou v $\eqRef{MSG}$ platí ```math f(x \iter m) = \min_{x \in X_m} f(x), ``` kde $X_m := \lin \set{h_0, \dots, h_{m-1}}$ (viz **Definice** $\secRefAt{2.1.6}{./Konvexní množiny}$ - lineární obal). Zejména pro $m = n$ dostáváme ```math f(x \iter n) = \min_{x \in \R^n} f(x), ``` tj. $x \iter n$ je řešením úlohy $\eqRef{3.2.1} \, \and \, \eqRef{MSG}$. > Nalezení $Q$**-sdružených** vektorů lze provést zobecněným **Gramm-Schmidtovým ortogonalizačním procesem** (ten je uveden v Lin. Alg. ve speciálním tvaru pro $Q = I$). Explicitně můžeme odvodit délku $k$-tého kroku jako ```math \a_k = - {h_k^T \grad f(x \iter k) \over h_k^T Q h_k} \eqT{3.2.9} ``` Celkem můžeme metodu popsat následovně ```math h_0 := -\grad f(x \iter 0), \quad h_k := -\grad f(x \iter k) + \beta_{k-1} h_{k-1} \eqT{3.2.10} ``` ```math \beta_{k-1} := {\gradT f(x \iter k) Q h_{k-1} \over h_{k-1}^T Q h_{k-1}} \eqT{3.2.11}, ``` přičemž body minimalizující posloupnosti jsou počítány podle **Věty** $\secRef{3.2.9}$. > Tento výpočet lze "zjednodušit", viz $(3.2.12)$ v přednášce. Hlavní výhodou **metody sdružených gradientů** je její **snadná implementace**, naopak nevýhodou citlivost na podmíněnost matice $Q$. Také se daří říct, že metoda sdružených gradientů **konverguje nejrychleji** z metod založených pouze na *maticovém násobení*. Pro nekvadratické funkce používáme stejný algoritmus jako doteď až na volbu $\beta_k$, ale metodu restartujeme po $n$ krocích ##### **Věta** $\secT{3.2.13}$ (Rychlost konvergence) Nechť $f \in C^3$ na $\R^n$, $x \iter 0 \in \R^n$ a $x^*$ je **nedegenerované lokální minimum**, tj. $\grad f(x^*) = 0$ a $\hess f(x^*) > 0$ Nechť $x \iter k$ je výsledek **metody sdružených gradientů** s cyklem délky $n$ a výchozím bodem $x \iter {k-1}$ a nechť $x \iter k \to x\str$ pro $k \to \infty$. Potom **minimalizující posloupnost** $\set{x \iter k}$ konverguje **superlineárně** s řádem **alespoň** $p = 2$. > MSG souvisí s metodami *Krylovových podprostorů*.