Home A - Z
Page Index

An Otter Wiki

Commit 1549fd

2026-03-28 10:21:00 Štěpán Zapadlo: Fix display math
matematické programování/numerické metody v rn.md ..
@@ 35,14 35,17 @@
```
</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}$$
+ ```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
- $$x^{[k+1]} = x^{[k]} + \a_k h_k,$$
+ ```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**.
@@ 51,70 54,83 @@
> 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]}),$$
+ ```math
+ 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]}))$$
+ ```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
- $$f(x) = \frac 1 2 \scal {Qx} x - x^T b \eqT{3.2.2},$$
+ ```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ě
- $$0 < \l_1 \leq \l_2 \leq \dots \leq \l_n$$
+ ```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
- $$g(x) := \grad f(x) = Qx - b,$$
+ ```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
- $$\a_k = {g_k^T g_k \over g_k^T Q g_k} \in [1/\l_n, 1/\l_1]$$
+ ```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í
- $$E(x) := f(x) - f(x^*) = \frac 1 2 (x - x^*)^T Q (x - x^*)$$
+ ```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í
- $$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]})$$
+ ```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
- $$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}$$
+ ```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
- $$\set{x \in \R^n \mid f(x) \leq f(x^{[0]})}$$
+ ```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$.
@@ 122,14 138,15 @@
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,$$
+ ```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
@@ 137,63 154,69 @@
- 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)$$
+ ```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
- $$\grad T_k(x) = \grad f(x^{[k]}) + \hess f(x^{[k]}) (x - x^{[k]}),$$
+ ```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
- $$x^{[k+1]} = x^{[k]} - (\hess f(x^{[k]}))^{-1} \grad f(x^{[k]})$$
+ ```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
- $$f(x) = \frac 1 2 x^T Q x - b^T x \eqT{MSG},$$
+ ```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
- $$Qx = b \eqT{MSGa},$$
+ ```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
- $$\scal {Qh_1} {h_2} = h_1^T Q h_2 = 0$$
+ ```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
- $$\scal {Q h_i} {h_j} = 0 \text{ pro } i \neq j$$
+ ```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é**.
@@ 201,36 224,45 @@
##### **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}$$
+ ```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í
- $$f(x \iter m) = \min_{x \in X_m} f(x),$$
+ ```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
- $$f(x \iter n) = \min_{x \in \R^n} f(x),$$
+ ```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
- $$\a_k = - {h_k^T \grad f(x \iter k) \over h_k^T Q h_k} \eqT{3.2.9}$$
+ ```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ě
- $$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
+ 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},$$
+ ```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)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9