Numerické metody v Rⁿ
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, \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
\[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 \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ě
\[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
\[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 \(\secT{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 \(\secRef{3.2.1}\) 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)}, \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
\[\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í
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
\[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
\[\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
\[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
\[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
\[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
\[\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
\[\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
\[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í
\[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
\[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
\[\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ě
\[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}\] \[\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ů.