Home A - Z
Page Index

An Otter Wiki

Commit ad5f37

2026-03-27 23:31:42 Štěpán Zapadlo: Add page about numerical methods for optimization in R
/dev/null .. matematické programování/numerické metody v r.md
@@ 0,0 1,207 @@
+ # 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{\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{\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{\hess}{1}{\nabla^2\, #1}
+ \letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1}
+ \letThereBe{\iter}{1}{^{[#1]}}
+ \letThereBe{\set}{1}{\left\{ #1 \right\}}
+ ```
+
+ </div>
+
+ ### Rychlost konvergence
+
+ ##### **Definice** $\secT{3.1}$
+ Nechť jsou dány 2 posloupnosti $\brackets{e_ k}_ {k = 0}^\infty$ a $\brackets{h_ k}_ {k = 0}^\infty$ takové, že
+
+ $$e_k \in [0, \infty), \quad e_k \to 0 \quad \and \quad h_k \in [0, \infty), \quad h_k \to 0.$$
+
+ Řekneme, že posloupnost $\brackets{e_k}$ konverguje **rychleji** (*pomaleji*) než $\brackets{h_k}$, pokud existuje index $\tilde k \in \N_0$ takový, že
+
+ $$e_k \leq_{(\geq)} h_k \quad \forall k \in [0, \infty) \cap \N_0$$
+
+ ##### **Definice** $\secT{3.2}$ (Rychlost konvergence)
+ Nechť je dána posloupnost $\brackets{e_ k}_ {k = 0}^\infty$ splňující $e_k \in [0, \infty)$ a $e_k \to 0$. Řekneme, že posloupnost $\brackets{e_k}$ konverguje
+ - **alespoň lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **rychleji** než **geometrická** posloupnost se členy tvaru $q \bar \beta^k$, kde $q > 0$ a $\bar \beta \in (\beta, 1)$.
+ - čím **větší** $\bar \beta$, tím **pomaleji** jde tato geometrická posloupnost k nule - tj. konverguje rychleji než geometrická posloupnost s $\bar \beta$ větší než $\beta$
+ - **nejvýše lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **pomaleji** než **geometrická** posloupnost se členy tvaru $q \bar \beta^k$, kde $q > 0$ a $\bar \beta \in (0, \beta)$.
+ - **lineárně s rychlostí** $\beta \in (0,1)$, pokud konverguje **nejvýše** a současně **alespoň** lineárně s rychlostí $\beta$.
+ - **superlineárně (*sublineárně*)**, pokud konverguje **rycheji** (*pomaleji*) než libovolná geometrická posloupnost se členy tvaru $q \beta^k$, kde $q > 0$ a $\beta \in (0,1)$.
+
+ ##### **Definice** $\secT{3.4}$
+ Nechť je dána posloupnost $\brackets{e_ k}_ {k = 0}^\infty$ splňující $e_k \in [0, \infty)$ a $e_k \to 0$, přičemž $\brackets{e_k}$ konverguje **superlineárně**. Řekneme, že posloupnost $\brackets{e_k}$ konverguje
+ - **alespoň superlineárně s řádem** $p > 1$, pokud konverguje **rychleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (1, p)$
+ - čím **větší** $\bar p$, tím **rychleji** posloupnost $q \beta^{\bar p^k}$ konverguje - tj. $\brackets{e_k}$ konverguje rychleji než všechny posloupnosti s **menším** $p$
+ - **nejvýše superlineárně s řádem** $p > 1$, pokud konverguje **pomaleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (p, \infty)$
+ - **superlineárně s řádem** $p > 1$, pokud konverguje **nejvýše** a současně **alespoň** superlineárně s *řádem* $p$.
+ - **superlineárně s řádem** $p = 1$, pokud konverguje **pomaleji** než všechny posloupnosti se členy tvaru $q \beta^{\bar p^k}$, kde $q > 0$ a $\beta \in (0,1)$ a $\bar p \in (1, \infty)$
+
+ ## Metody
+
+ ##### **Definice** $\secT{3.1.1}$ (Unimodální funkce)
+ Nechť je dán interval $I \subset \R$ a funkce $f: I \to \R$. Řekneme, že $f$ je ***unimodální*** na $I$, jestliže existuje $x^*\in I$ takové, že
+ - $f(x_1) > f(x_2)$ pro libovolná $x_1, x_2 \in I$ splňující $x^*> x_1 > x_2$
+ - $f(x_1) < f(x_2)$ pro libovolná $x_1, x_2 \in I$ splňující $x^*< x_1 < x_2$
+
+ ---
+
+ Jinými slovy, **unimodální** funkce je **klesající** na $(-\infty, x^*) \cap I$ (tj. *nalevo* od $x^*$) a **rostoucí** na $I \cap (x^*, \infty)$ (tj. *napravo* od $x^*$).
+
+ > Unimodalita **neimplikuje** konvexnost (*ani se spojitostí*), pouze **kvazikonvexnost**
+ >
+ > Naopak, *konvexní* funkce **nemusí** nutně být *unimodální* (ale **ostrá konvexnost** $\implies$ **unimodalita**)
+ > > Konvexní funkce nemusí být např. jen rostoucí, ale i **neklesající**
+
+
+ V této části budeme řešit úlohu
+
+ $$f(x) \to \min, \qquad x \in I := [a,b] \eqT{3.1.1}$$
+
+ ##### **Lemma** $\secT{3.1.2}$
+ Nechť $f: I \to \R$ je **unimodální** na $I$ a $x_1, x_2 \in I$ jsou takové, že $x_1 < x_2$.
+ - Je-li $f(x_1) \leq f(x_2)$, pak $x^*\leq x_2$
+ - Je-li $f(x_1) \geq f(x_2)$, pak $x^*\geq x_1$
+
+ ---
+
+ ***Upozornění:*** \
+ Dále uvažujme <a style="color: red">***POUZE UNIMODÁLNÍ***</a> funkce.
+
+ Navíc nechť $N$ značí **povolený počet vyčíslení** a **přesnost** těchto metod je dáno jako $|\bar x - x^*|$, kde $x^*$ je **přesné** řešení úlohy $\eqRef{3.1.1}$ a $\bar x$ jeho nalezená aproximace.
+
+ ### Metoda prostého dělení
+
+ > Tato metoda **není** efektivní a je to *de facto* hrubá síla
+
+ Podle parity $N$ určíme dělící body intervalu $I$.
+
+ <center>
+
+ | $N$ **liché** | $N$ **sudé**
+ | -- | --
+ $$x_i := a + {b - a \over N + 1} i, \quad i=1, \dots, N = 2k - 1$$ | $$x_{2i} := a + {b - a \over k + 1} i \quad \and \quad x_{2i - 1} := x_{2i} - \delta, \\ i = 1, \dots, k := N/2,$$
+
+ </center>
+
+ kde $\delta$ je *vhodné malé číslo.*
+
+ Poté vyčíslíme $f(x_1), \dots, f(x_N)$ (což v případě $N$ **sudého** a $\delta \in \set{0, {b-a \over k+ 1}}$ znamená **pouze** $k$ vyčíslení) a nechť v $x_j$ nastává nejmenší hodnota, tj.
+
+ $$f(x_j) = \min_{1 \leq i \leq N} f(x_i)$$
+
+ Pak z **Lemma** $\secRef{3.1.2}$ plyne, že $x^*\in [x_{j-1}, x_{j+1}]$ a tento interval nazveme **interval lokalizace minima (ILM)** a za aproximaci $x^*$ vezmeme *střed* ILM, tj. $\bar x := {x_{j-1} + x_{j+1} \over 2}$
+
+ Pro **délku** $l_N$ *intervalu lokalizace minima* platí
+
+ $$l_N := \max_{1 \leq i \leq N} (x_{i+1} - x_{i-1}) = \lcases{2 {b - a \over N+1}, & N = 2k - 1 \\ {b - a \over (N/2) + 1} + \delta, & N = 2k}$$
+
+ > Pro $N$ **sudé** je **poslední** interval delší, proto dostáváme takový tvar $l_N$
+
+ > Přesnost této metody je dána **polovinou ILM**, tj. ${l_N \over 2}$
+
+ Rychlost konvergence této metody je **sublineární**, navíc je tento algoritmus **pasivní**, tj. volba $x_{m+1}$ **nezáleží** na $x_1, \dots, x_m$ (závisí pouze na $N$, či na $N$ a $\delta$).
+
+ > Při rovnosti funkčních hodnot **preferujeme konec** (*teoreticky by to mělo být jedno*)
+
+ ### Metoda půlení intervalu <a name="mpi"></a>
+
+ Nechť nyní $N = 2k$. Položme $a_0 = a$, $b_0 = b$ a
+
+ $$x_i^- := {a_{i-1} + b_{i-1} \over 2} - \delta \quad \and \quad x_i^+ := {a_{i-1}+b_{i-1} \over 2} + \delta,$$
+
+ kde $\delta > 0$ je *dostatečně malé* a $i = 1, \dots, k$. Vyčíslíme funkci v $x_i^-, x_i^+$, tj. dostaneme $f(x_i^-), f(x_i^+)$. Pak
+ - jestliže $f(x_i^-) < f(x_i^+)$, pak podle **Lemma** $\secRef{3.1.2}$ je **ILM** $[a_{i-1}, x_i^+] \implies a_i = a_{i-1}, b_i = x_i^+$
+ - jestliže $f(x_i^-) > f(x_i^+)$, pak podle **Lemma** $\secRef{3.1.2}$ je **ILM** $[x_i^-, b_{i-1}] \implies a_i = x_i^-, b_i = b_{i-1}$
+
+ Takto můžeme tento proces opakovat ($k$-krát, jelikož máme $N = 2k$ povolených vyčíslení), kdy za $a,b$ volíme krajní body *ILM* pro každý krok. Zřejmě, jako aproximaci $x^*$ v $k$-tém kroku bereme *střed ILM* pro $k$-tý krok.
+
+ Délka *ILM* je v tomto případě
+
+ $$l_k = {b - a\over 2^k} + {(2^k - 1)\delta \over 2^{k-1}},$$
+
+ přičemž $\delta \in [0, {b-a\over 2}]$ a navíc pro $k \to \infty$ je $l_k \to 2\delta$.
+
+ > Z tohoto vyplývá, že čím menší $\delta$, tím je metoda přesnější. Nicméně ve skutečnosti se můžeme dostat k zaokrouhlovacím chybám, které dokonce mohou způsobit, že špatně určíme velikosti $f(x_i^-), f(x_i^+)$ (tím pádem bychom řekli, že $x^*$ je v opačném intervalu, než je ve skutečnosti)
+
+ Tato metoda konverguje **lineárně** s rychlostí $1/2$.
+
+ > Při rovnosti funkčních hodnot **zapomínáme konec** (*teoreticky by to mělo být jedno*)
+
+ ### Metoda zlatého řezu<a name="mzr"></a>
+
+ Myšlenka metody zlatého řezu "*vylepšuje*" metodu půlení intervalu tak, že každá další iterace umožňuje pouze **jedno** další vyčíslení.
+
+ > Zde $\tau$ je řešení rovnice $\tau^2 - \tau - 1 = 0$, tj. a $\frac 1 \tau \approx 0.618$
+
+ Mějme funkci $f$, interval $[a,b]$, přesnost $\ve$ nebo počet vyčíslení $N \geq 2$:
+ 1. (*Inicializace*) Položíme $a_0 := a, b_0 := b$ a $k := 1$. Vypočteme
+
+ ```math
+ \l_1 := a_0 + {b_0 - a_0 \over \tau^2} \quad \and \quad \mu_1 := a_0 + {b_0 - a_0 \over \tau}
+ ```
+
+ 2. Je-li $k = N$, pokračujeme částí 5., jinak následuje krok 3.
+ 3. Vyčíslíme $f(\l_k)$ a $f(\mu_k)$. Jestliže $f(\l_k) \geq f(\mu_k)$:
+ 1. Položíme $a_k := \l_k, b_k = b_{k-1}, \l_{k+1} := \mu_k$ a
+
+ ```math
+ f(\l_{k+1}) := f(\mu_k), \quad \mu_{k+1} := a_k + {b_k - a_k \over \tau}
+ ```
+
+ a pokračujeme na krok 4.
+ 2. Položíme $a_k := a_{k-1}, b_k := \mu_k, \mu_{k+1} := \l_k$ a
+
+ ```math
+ f(\mu_{k+1}) := f(\l_k), \quad \l_{k+1} := a_k + {b_k - a_k \over \tau^2}
+ ```
+
+ a pokračujeme na krok 4.
+ 4. Položíme $k := k+1$ a pokračujeme krokem 2.
+ 5. Stanovíme poslední *ILM* jako $[a_{k-1}, b_{k-1}]$ a vypočteme $\bar x := {a_{k-1} + b_{k-1} \over 2}$. **KONEC**
+
+ Tato metoda konverguje **lineárně** s rychlostí $\frac 1 \tau \approx 0.618$
+
+ > Toto **neznamená**, že by **na stejný počet vyčíslení** byla tato metoda horší než [metoda půlení intervalu](#mpi)
+
+ [![](https://bookstack.zapadlo.name/uploads/images/gallery/2023-01/scaled-1680-/image-1672866479411.png)](https://bookstack.zapadlo.name/uploads/images/gallery/2023-01/image-1672866479411.png)
+
+ ### Fibonacciho metoda
+
+ V této poslední metodě uvažujme, že zkrácení $\delta$ může být **jiné** v každé kroku metody.
+
+ > Nechť $F_n$ je $n$-té Fibonacciho číslo
+
+ Máme povoleno $N$ vyčíslení, takže $M = N - 1$ a
+
+ $$\l_i = a_{i - 1} + {F_{N - i -1} \over F_{N - i + 1}} l_{i-1} = b_{i-1} - {F_{N - 1} \over F_{N - 1 + i}} l_{i-1}$$
+
+ $$\mu_i = a_{i-1} + {F_{N - 1} \over F_{N - 1 + i}} l_{i-1} = b_{i-1} - {F_{N - i -1} \over F_{N - i + 1}} l_{i-1}$$
+
+ [![](https://bookstack.zapadlo.name/uploads/images/gallery/2023-01/scaled-1680-/image-1672583724613.png)](https://bookstack.zapadlo.name/uploads/images/gallery/2023-01/image-1672583724613.png)
+
+ Tato metoda konverguje **lineárně** s rychlostí $\frac 1 \tau \approx 0.618$, tj. *stejně* jako [metoda zlatého řezu](#mzr)
+
+ > Fibonacciho metoda je (*mírně*) přesnější, než *metoda zlatého řezu* (která lze vnímat jako *limitní varianta* Fibonacciho metody). Nicméně u Fibonacciho metody je při změně $N$ potřeba **všechny body přepočítat**, což u metody zlatého řezu **není**.
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