<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

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

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

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^*)$$

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

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

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

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

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

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

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

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

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

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

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

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