<div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0">

</div>

Budeme se věnovat úlohám (přesněji numerickým metodám jejich řešení) typu

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

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**.

U této metody volíme

přičemž délku kroku volíme **přesným řešením** úlohy

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).

Nechť $f$ je kvadratická funkce tvaru

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ě

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

tedy v jednotlivých iteracích dostáváme $g_k := Qx^{[k]} - b$ a $\a_k$ můžeme určit jako

Nyní se zaměříme na konvergenci metody, kterou můžeme zkoumat pomocí

Platí

---

Z Lemmatu $\secRef{3.2.1}$ okamžitě plyne, že pokud pro nějaké $k \in \N$ nastane

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]}$

V případě nekvadratické funkce je metoda největšího spádu schopna nalézt **pouze stacionární body**.

Nechť $f: \R^n \to \R$ je **spojitě diferencovatelná**. Jestliže bod $x^{[0]} \in \R^n$ je takový, že množina

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í

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$

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

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.

Tedy místo funkce $f$ uvažujeme v $k$-tém kroku

Jelikož hledáme řešení $T_k(x) \to \min$, tak výraz výše první zderivujme, z čehož dostaneme

což v případě ***regulární*** matice $\hess f(x^{[k]})$ vede na

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.

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*).

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í)

Uvažujme situaci v úloze $\eqRef{3.2.1}$, kdy máme funkci

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

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.

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

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

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é**.

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

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í

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

tj. $x \iter n$ je řešením úlohy $\eqRef{3.2.1} \, \and \, \eqRef{MSG}$.

Explicitně můžeme odvodit délku $k$-tého kroku jako

Celkem můžeme metodu popsat následovně

přičemž body minimalizující posloupnosti jsou počítány podle **Věty** $\secRef{3.2.9}$.

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

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$.