Numerické metody v R^n
$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\hess#1{\nabla^2\, #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} $$
Budeme se věnovat úlohám (přesněji numerickým metodám jejich řešení) typu $$ f(x) \to \min, \quad x \in \R^n, \tag{\T{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 $$ 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 $$ h_k = - \grad f(x^{[k]}), $$ přičemž délku kroku volíme přesným řešením úlohy $$ 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 $$ f(x) = \frac 1 2 \scal {Qx} x - x^T b \tag{\T{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ě $$ 0 < \l_1 \leq \l_2 \leq \dots \leq \l_n $$ Díky tomu můžeme úlohu $\tagEq{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 $$ 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 $$ \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í $$ E(x) := f(x) - f(x^* ) = \frac 1 2 (x - x^* )^T Q (x - x^* ) $$
Lemma $\D{3.2.1}$ (Konvergence metody největšího spádu)
Platí $$ 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 $\tagDe{3.1.2}$ okamžitě plyne, že pokud pro nějaké $k \in \N$ nastane $$ 1 = {(g_k^T g_k)^2 \over (g_k^T Q g_k)(g_k^T Q^{-1} g_k)}, \tag{\T{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 $\tagEq{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 $\D{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 $$ \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í $$ 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í
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 $$ 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$