Commit 64b62f
2026-03-27 23:42:23 Štěpán Zapadlo: Numerické Metody V R^N deleted.| matematické programování/numerické metody v r^n.md .. /dev/null | |
| @@ 1,239 0,0 @@ | |
| - | # Numerické metody v Rⁿ |
| - | |
| - | <div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0"> |
| - | |
| - | ```math |
| - | \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}} |
| - | \letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\addLabel}{2}{\cssId{#1-#2}{\text{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}} |
| - | \letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addLabel{sec}{#1}} |
| - | \letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}} |
| - | \letThereBe{\eqRefAt}{2}{\href{#2\#eq-#1}{(\text{#1})}} |
| - | \letThereBe{\secRefAt}{2}{\href{#2\#sec-#1}{(\text{#1})}} |
| - | \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}} |
| - | \letThereBe{\rcases}{1}{\left.\begin{align}#1\end{align}\right\}} |
| - | \letThereBe{\rcasesAt}{2}{\left.\begin{alignat}{#1}#2\end{alignat}\right\}} |
| - | \letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}} |
| - | \letThereBe{\lcasesAt}{2}{\left\{\begin{alignat}{#1}#2\end{alignat}\right.} |
| - | \letThereBe{\scal}{2}{\langle #1, #2 \rangle} \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \LetThereBe{\dist}{\rho} |
| - | \LetThereBe{\and}{\&}\letThereBe{\brackets}{1}{\left\{ #1 \right\}} |
| - | \letThereBe{\parc}{2}{\frac {\partial #1}{\partial #2}} |
| - | \letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}} |
| - | \letThereBe{\bm}{1}{\boldsymbol{#1}} \letThereBe{\mcal}{1}{\mathcal{#1}} |
| - | \letThereBe{\vv}{1}{\mathbf{#1}}\letThereBe{\vvp}{1}{\pmb{#1}} |
| - | \LetThereBe{\ve}{\varepsilon} \LetThereBe{\l}{\lambda} \LetThereBe{\th}{\vartheta} \LetThereBe{\a}{\alpha} \LetThereBe{\vf}{\varphi} |
| - | \letThereBe{\conv}{1}{\mathrm{conv}\, #1} \letThereBe{\cone}{1}{\mathrm{cone}\, #1} |
| - | \letThereBe{\aff}{1}{\mathrm{aff}\, #1} \letThereBe{\lin}{1}{\mathrm{Lin}\, #1} \letThereBe{\span}{1}{\mathrm{span}\, #1} |
| - | \LetThereBe{\O}{\mathcal O} |
| - | \letThereBe{\ri}{1}{\mathrm{ri}\, #1} \letThereBe{\rd}{1}{\mathrm{r}\partial\, #1} \letThereBe{\interior}{1}{\mathrm{int}\, #1} |
| - | \LetThereBe{\proj}{\Pi} \letThereBe{\epi}{1}{\mathrm{epi}\, #1} |
| - | \letThereBe{\grad}{1}{\mathrm{grad}\, #1} \letThereBe{\gradT}{1}{\mathrm{grad}^T #1} \letThereBe{\gradx}{1}{\mathrm{grad}_x #1} \letThereBe{\hess}{1}{\nabla^2\, #1} \letThereBe{\hessx}{1}{\nabla^2_x #1} \letThereBe{\jacobx}{1}{D_x #1} \letThereBe{\jacob}{1}{D #1} |
| - | \letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1} |
| - | \letThereBe{\iter}{1}{^{[#1]}} \LetThereBe{\str}{^*} |
| - | \LetThereBe{\spv}{\mcal V} \LetThereBe{\civ}{\mcal U} |
| - | \LetThereBe{\knvxProg}{\eqRefAt{4.1}{./nutne-a-postacujici-podminky-optimality} \, \and \, \eqRefAt{4.2}{./nutne-a-postacujici-podminky-optimality}} |
| - | \letThereBe{\set}{1}{\left\{ #1 \right\}} |
| - | ``` |
| - | |
| - | </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**. |
| - | |
| - | > 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ů*. |