The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b0b33opt [2025/06/04 14:00] – [Vlastní čísla a vektory] zapleka3
+++ statnice:bakalar:b0b33opt [2025/06/12 10:33] (current) – [Podmínky konvexity podle derivací] el_dusto
@@ Line 1: / Line 1: @@
-==== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita. ====
+====== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita. ======
 [[https://fel.cvut.cz/cz/education/bk/predmety/46/74/p4674306.html|B0B33OPT]] [[https://cw.fel.cvut.cz/wiki/courses/B0B33OPT|Webové stránky předmětu]]
@@ Line 258: / Line 258: @@
 %%<mjax>g(x) = x^T A x + b^T x + c</mjax>%%
+Tato funkce obsahuje jak kvadratický, tak lineární člen – jejím cílem je najít stacionární bod a rozhodnout, zda jde o minimum, maximum nebo sedlový bod.
 **Doplnění na n-tý řád (Taylorův polynom):**
@@ Line 288: / Line 289: @@
-===== Optimální proložení bodů podprostorem (PCA) =====
+===== 3. Optimální proložení bodů podprostorem (PCA) =====
-**Motivace:** Ve strojovém učení nebo klasifikaci často pracujeme s daty ve velmi vysoké dimenzi (např. tisíce či miliony rysů). PCA a SVD umožňuje „zcvrknout“ tyto rozměry na menší podprostor tak, aby se zachoval co největší rozptyl (informace) – usnadní to vizualizaci, zrychlí algoritmy a sníží šum.
+Tato kapitola se věnuje metodám, které hledají **nejlepší aproximaci dat** v nižším rozměru. Typickým příkladem je metoda hlavních komponent (**PCA**), která minimalizuje ztrátu informace při promítání dat do podprostoru. Klíčovým nástrojem pro tuto úlohu je **singulární rozklad matice (SVD)** – univerzální technika pro analýzu struktury a „redukování“ matic.
-PCA lze chápat dvojím způsobem:
+**Motivace:** Ve strojovém učení nebo klasifikaci často pracujeme s daty ve velmi vysoké dimenzi (např. tisíce rysů). PCA umožňuje zmenšit rozměr na menší podprostor tak, aby se zachoval co největší rozptyl (informace). To vede k rychlejším výpočtům, nižšímu šumu a přehlednější vizualizaci.
-**1. Minimální vzdálenost od podprostoru:**
+==== Singulární rozklad matice (SVD) ====
-Hledáme ortonormální matici \(X\in\mathbb{R}^{m\times k}\) tak, aby
-%%<mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>%%
-<abbr title="promítá data na k-dimenzionální podprostor a minimalizuje součet čtverců reziduí">❓</abbr>
-**2. Maximální zachycený rozptyl (stopa):**
+Každou reálnou matici \( A \in \mathbb{R}^{m \times n} \) lze zapsat ve tvaru:
-Volíme \(X\) tak, aby projekce dat na podprostor měla co největší celkový rozptyl, tj.
+%%<mjax>A = U \Sigma V^T</mjax>%%
-%%<mjax>\max_{X^{T}X=I}\sum_{i=1}^{n}\|X^{T}a_{i}\|_{2}^{2}
+<abbr title="U a V jsou ortogonální matice, Σ je diagonální matice se singulárními čísly.">❓</abbr>
-= \max_{X^{T}X=I}\|X^{T}A\|_{F}^{2}
-= \max_{X^{T}X=I}\mathrm{tr}\bigl(X^{T}A A^{T}X\bigr)</mjax>%%
-<abbr title="Hledáme k nejvýznamnějších dimenzí v datech, na kterých je součet variancí maximální">❓</abbr>
-=== Funkce stopa (trace) ===
+  * \( U \in \mathbb{R}^{m \times m} \) – levé singulární vektory
+  * \( \Sigma \in \mathbb{R}^{m \times n} \) – diagonální matice singulárních čísel
+  * \( V \in \mathbb{R}^{n \times n} \) – pravé singulární vektory
-Stopa matice \(A\in\mathbb{R}^{n\times n}\) je součet jejích diagonálních prvků:
+Singulární čísla \( \sigma_1 \ge \cdots \ge \sigma_r > 0 \) jsou druhé odmocniny vlastních čísel matic \( A A^T \) a \( A^T A \). SVD existuje pro každou reálnou (i obdélníkovou) matici.
-%%<mjax>\mathrm{tr}(A) = \sum_{i=1}^{n}A_{ii}</mjax>%%
+**Výpočet SVD:**
-<abbr title="stopa odpovídá součtu vlastních čísel a je invariantní vůči podobnosti">❓</abbr>
+  * Spočteme spektrální rozklad \( A A^T = U S U^T \) a \( A^T A = V S V^T \)
+  * Singulární čísla \( s_i = \sqrt{S_{ii}} \)
+  * Pak \( A = U S^{1/2} V^T \)
-=== Výpočet PCA (kuchařka) s příkladem ===
+==== PCA jako optimalizační úloha ====
-. Spočtěte matici kovariancí
-%%<mjax>S = A\,A^{T}</mjax>%%
-. Najděte spektrální rozklad
-%%<mjax>S = V\,\Lambda\,V^{T},\quad \lambda_{1}\ge\cdots\ge\lambda_{m}</mjax>%%
-. Rozdělte ortonormální bázi \(V = [\,X\mid Y\,]\)
+PCA můžeme chápat dvěma způsoby:
-. Projekce dat na \(k\)-rozměrný podprostor:
-%%<mjax>\widehat A = X\,X^{T}A</mjax>%%
-. Chyba proložení:
-%%<mjax>\|A-\widehat A\|_{F}^{2} = \sum_{i=k+1}^{m}\lambda_{i}</mjax>%%
-**Příklad pro**
+  * **Minimalizace chyby projekce (minimální vzdálenost od podprostoru):**
-%%<mjax>A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\;k=1.</mjax>%%
+    * Hledáme podprostor dimenze \(k\), na který promítneme data tak, aby se minimalizoval součet čtverců vzdáleností (reziduí):
-- %%<mjax>S = AA^{T} = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}</mjax>%%
+    * %%<mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>%%<abbr title="Promítáme data na podprostor a chceme co nejmenší součet kvadratických chyb.">❓</abbr>
-- Eigen: %%<mjax>\lambda_{1}=9,\;\lambda_{2}=1, \;v_{1}=\tfrac1{\sqrt2}\!\begin{pmatrix}1\\1\end{pmatrix}</mjax>%%
-- %%<mjax>X = [v_{1}]\,,\quad \widehat A = X X^{T}A
-= \tfrac12\begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}2&1\\1&2\end{pmatrix}
-= \begin{pmatrix}1.5&1.5\\1.5&1.5\end{pmatrix}</mjax>%%
-- Chyba proložení: %%<mjax>\|A-\widehat A\|_{F}^{2} = \lambda_{2} = 1</mjax>%%
-  * **Interpretace:** PCA hledá chybu, kterou uděláme, když z matice \(A\) zahodíme \(m-k\) dimenzí a data optimálně promítneme do podprostoru dimenze \(k\). Tato chyba je dána součtem čtverců „Zahozených“ singulárních čísel:
+  * **Maximalizace zachyceného rozptylu (stopa):**
+    * Volíme \(X\) tak, aby projekce dat na podprostor měla co největší rozptyl:
+    * %%<mjax>\max_{X^{T}X=I}\sum_{i=1}^{n}\|X^{T}a_{i}\|_{2}^{2}= \max_{X^{T}X=I}\|X^{T}A\|_{F}^{2}= \max_{X^{T}X=I}\mathrm{tr}\bigl(X^{T}A A^{T}X\bigr)</mjax>%%<abbr title="Hledáme k nejvýznamnějších dimenzí v datech, na kterých je součet variancí maximální">❓</abbr>
-===== Singulární rozklad matice (SVD) =====
+Tyto dva přístupy vedou ke stejnému výsledku – podprostoru generovanému prvními \(k\) vlastními vektory matice \(A A^T\).
-**Definice:** Pro libovolnou matici \(A\in\mathbb{R}^{m\times n}\) existují ortogonální matice
+=== Aproximace maticí nižší hodnosti ===
-\(U\in\mathbb{R}^{m\times m}\), \(V\in\mathbb{R}^{n\times n}\) a diagonální matice
-\(\Sigma\in\mathbb{R}^{m\times n}\) se singulárními čísly
-\(s_{1}\ge s_{2}\ge\cdots\ge s_{p}\ge0\) \((p=\min\{m,n\})\),
-že
-%%<mjax>A = US V^{T}</mjax>%%
-<abbr title="U, V mají ortonormální sloupce (levé a pravé singulární vektory), S obsahuje singulární čísla">❓</abbr>
-**Výpočet SVD:**
+Nechť \( A \in \mathbb{R}^{m \times n} \), \( p = \min\{m,n\} \) a \( k \le p \).
+Hledáme matici \( B \) hodnosti nejvýše \( k \), která je co nejblíže původní matici \( A \) ve Frobeniově normě:
-. Spočtěte matice
+%%<mjax>\min_{\mathrm{rank}(B) \le k} \|A - B\|_F</mjax>%%
-%%<mjax>AA^{T}=U\,S\,U^{T},\quad A^{T}A=V\,S\,V^{T}</mjax>%%
+<abbr title="Snažíme se najít nejlepší možnou aproximaci A pomocí matice nižší hodnosti.">❓</abbr>
-<abbr title="S je diagonální matice s_i^2, vlastní čísla AAᵀ a AᵀA">❓</abbr>
-. Sloupce U jsou vlastní vektory matice \(AA^{T}\), sloupce V vlastní vektory \(A^{T}A\).
+== Eckart–Youngova věta ==
-. Singulární čísla \(s_{i}=\sqrt{S_{ii}}\).
+Tato úloha má řešení dáno oříznutím SVD rozkladu \( A = U \Sigma V^T \) na prvních \( k \) složek:
-===Eckart–Youngova věta===
-Nechť \(A\in\mathbb{R}^{m\times n}\), \(p=\min\{m,n\}\) a \(k\le p\). Řešením úlohy
-%%<mjax>\min_{\mathrm{rank}(B)\le k}\|A - B\|_{F}^{2}</mjax>%%
-je matice
 %%<mjax>
-B^{*}
+A_k = \sum_{i=1}^{k} s_i\,u_i\,v_i^T = U\,\Sigma_k\,V^T
-= U\,S_{k}\,V^{T}
+</mjax>%%
-= \sum_{i=1}^{k} s_{i}\,u_{i}\,v_{i}^{T}
-</mjax>%%
 kde
 %%<mjax>
-S_{k}
+\Sigma_k = \mathrm{diag}(s_1, \dots, s_k, 0, \dots, 0) \in \mathbb{R}^{m \times n}
-= \mathrm{diag}(s_{1},\dots,s_{k},0,\dots,0)\in\mathbb{R}^{p\times p}
 </mjax>%%
+obsahuje jen první \( k \) singulárních čísel a zbytek nulujeme.
-**Aplikace SVD:**
+Používáme tedy jen první \( k \) singulárních složek z rozkladu SVD – to zaručuje nejlepší možnou aproximaci v dané dimenzi.
-  * Data-redukce, PCA
-  * Řešení nesingulárních či přeurčených soustav
-  * Komprese obrázků (low-rank aproximace)
-  * Výpočet pseudoinverzí a regularizace
-===== Globální a lokální extrémy funkce na podmnožině ℝⁿ =====
+=== Funkce stopa (trace) ===
-Nechť \(f: D \subseteq \mathbb{R}^{n} \to \mathbb{R}\), kde \(D\) je podmnožina ℝⁿ.
+Stopa čtvercové matice je součet diagonálních prvků:
+%%<mjax>\mathrm{tr}(A) = \sum_{i=1}^{n} A_{ii}</mjax>%%
+<abbr title="Stopa odpovídá součtu vlastních čísel a hraje roli v maximalizaci rozptylu.">❓</abbr>
-=== Definice globálních a lokálních extrémů ===
+Stopu si můžeš představit jako míru „energie“ nebo rozptylu, kterou matice zachytává v prostoru – čím větší stopa, tím více informací.
-  * **Globální minimum**:
-bod \(x^{*}\in D\) je globální minimum, pokud
+==== Výpočet PCA (krok za krokem) ====
-%%<mjax>f(x^{*}) \le f(x)\quad \forall\,x\in D.</mjax>%%
-  * **Globální maximum**:
-bod \(x^{*}\in D\) je globální maximum, pokud
+. Spočítáme matici kovariancí:  %%<mjax>S = A A^T</mjax>%%
-%%<mjax>f(x^{*}) \ge f(x)\quad \forall\,x\in D.</mjax>%%
+  * Matice \(S = A A^T\) je tzv. kovarianční matice, která říká, jak moc a v jakých směrech se data mění.
-  * **Lokální minimum**:
-bod \(x^{*}\in D\) je lokální minimum, pokud existuje otevřené okolí \(U \subset D\) takové, že
+. Provedeme spektrální rozklad: %%<mjax>S = V \Lambda V^T,\quad \lambda_1 \ge \cdots \ge \lambda_m</mjax>%%
-%%<mjax>f(x^{*}) \le f(x)\quad \forall\,x\in U.</mjax>%%
-  * **Lokální maximum**:
-bod \(x^{*}\in D\) je lokální maximum, pokud existuje otevřené okolí \(U \subset D\) takové, že
+. Zvolíme první \(k\) vektorů: \( V = [X \mid Y] \)
-%%<mjax>f(x^{*}) \ge f(x)\quad \forall\,x\in U.</mjax>%%
-Pokud je \(f\) konvexní na celém oboru \(D\), pak lokální minimum je zároveň globálním minimem; obdobně pokud je \(f\) konkávní, pak lokální maximum je globálním maximem.
+. Projekce dat: %%<mjax>\widehat{A} = X X^T A</mjax>%%
-Pro nalezení lok min a max použijeme Hessovu matici a nulové první derivace.
+. Chyba projekce: %%<mjax>\|A - \widehat{A}\|_F^2 = \sum_{i=k+1}^m \lambda_i</mjax>%%  <abbr title="Součet energií zahozených komponent – ztracený rozptyl.">❓</abbr>
-===== Vázané extrémy pomocí Lagrangeových multiplikátorů =====
-Pokud pro funkci \(f(x)\) hledáme extrém pod podmínkami
+=== Příklad ===
-\[
-g_{i}(x)=0,\quad i=1,\dots,m,
-\]
-postupujeme následovně:
-**Lagrangeova funkce:**
+Nechť:
+%%<mjax>A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\quad k = 1</mjax>%%
-  Definujeme
-%%<mjax>\mathcal{L}(x,\lambda) = f(x) - \sum_{i=1}^{m} \lambda_{i}\,g_{i}(x)</mjax>%%
-  kde \(\lambda = (\lambda_{1},\dots,\lambda_{m})\) jsou Lagrangeovy multiplikátory.
-**Nutné podmínky (stacionární body) na hladké části povrchu:**
+. Kovarianční matice: %%<mjax>S = A A^T = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}</mjax>%%
-Hledáme \((x^{*},\lambda^{*})\) tak, aby
+. Spektrální rozklad: %%<mjax>\lambda_1 = 9,\quad \lambda_2 = 1,\quad v_1 = \tfrac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}</mjax>%%
-%%<mjax>\nabla_{x}\mathcal{L}(x^{*},\lambda^{*}) = 0, g_{i}(x^{*}) = 0,\;i=1,\dots,m</mjax>%%
-<abbr title="∇ₓL=0 zajišťuje stacionaritu na povrchu definovaném rovnostmi g_i=0">❓</abbr>
-**Kontrola hranic domény (pokud je doména omezená nebo existují jiné ohraničení):**
+. Výběr podprostoru: %%<mjax>X = [v_1]</mjax>%%
-Kromě vnitřních stacionárních bodů na povrchu \(\{g_i(x)=0\}\) je třeba zkontrolovat i body, kde povrch naráží na hranici původní množiny \(D\) (např. krajní body, rohy). V těchto bodech se gradient \(\nabla_{x}\mathcal{L}\) nemusí rovnat nule, ale mohou vzniknout extrémy právě kvůli hranici. Zároveň musíme vyšetřit i původní funkci \(f(x)\) pro extrémy, které spadnou do omezení.
-**Druhé řádové podmínky (určení typu extrému) na povrchu:**
+. Projekce: %%<mjax>\widehat{A} = X X^T A = \tfrac{1}{2} \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix} = \begin{pmatrix}1.5 & 1.5\\1.5 & 1.5\end{pmatrix}</mjax>%%
-Označme Hessian Lagrangeovy funkce vzhledem k \(x\) jako
-%%<mjax>H(x,\lambda) = \nabla^{2}_{xx}\mathcal{L}(x,\lambda).</mjax>%%
-  Pro každý kandidátní bod \(x^{*}\) (splňující \(g_i(x^{*})=0\) a případně ležící na hranici domény) zkontrolujeme definitnost zrestrikovaného Hessianu \(H(x^{*},\lambda^{*})\) na podprostoru tangentu k množině \(\{g_{i}(x)=0\}\):
-  * Pokud je zrestrikovaný Hessian pozitivně definitní, pak \(x^{*}\) je lokální minimum.
-  * Pokud je zrestrikovaný Hessian negativně definitní, pak \(x^{*}\) je lokální maximum.
-  * Jinak je \(x^{*}\) sedlovým bodem na povrchu definovaném omezeními.
-<abbr title="kontrola Hessianu na podprostoru tangentu zajišťuje, že extrém leží na povrchu omezení">❓</abbr>
-**Výběr globálního extrému na omezeném prostoru:**
+. Chyba proložení: %%<mjax>\|A - \widehat{A}\|_F^2 = \lambda_2 = 1</mjax>%%
-  Z nalezených stacionárních bodů \(x^{*}\) (na povrchu a případně na hranici domény) vybereme ty, které splňují druhé řádové podmínky pro požadovaný typ (minimum nebo maximum) a porovnáme jejich hodnoty \(f(x^{*})\). Nejmenší (nebo největší) hodnota mezi nimi je globálním extrémem na omezeném množině.
+**Interpretace:** Projekce do 1D podprostoru zachová rozptyl \( \lambda_1 \), ztráta informace odpovídá \( \lambda_2 \). PCA tedy dává nejlepší možnou redukci na danou dimenzi.
-===== Úloha lineárního programování (LP) =====
+===== 4. Globální a lokální extrémy funkce na podmnožině ℝⁿ =====
+Extrémy mohou být:
+  * **volné**, tj. hledáme optimum na celé \(\mathbb{R}^n\),
+  * nebo **vázané**, kdy je funkce omezena podmínkami.
+V praxi často hledáme nejlepší řešení (např. nejnižší cenu, nejkratší trasu, maximální efektivitu), ať už bez omezení, nebo podmíněně – třeba za předpokladu omezených zdrojů.
+==== Definice ====
+Mějme funkci \( f: D \subset \mathbb{R}^n \rightarrow \mathbb{R} \).
+  * **Lokální minimum**: existuje okolí \( U \) bodu \( x^* \), že pro všechna \( x \in U \cap D \):  %%<mjax>f(x) \ge f(x^*)</mjax>%%
+  * **Lokální maximum**:  %%<mjax>f(x) \le f(x^*)</mjax>%%
+  * **Globální minimum** (na \(D\)):  %%<mjax>f(x) \ge f(x^*)\quad\forall x \in D</mjax>%%
+  * **Globální maximum**:  %%<mjax>f(x) \le f(x^*)\quad\forall x \in D</mjax>%%
+Lokální extrém je jen „nejlepší v okolí“, zatímco globální je nejlepší **v celé množině**.
+==== Kdy je extrém globální ====
+Pokud je funkce **konvexní**, pak **každé lokální minimum je zároveň globální minimum**. U konkávních funkcí analogicky pro maxima.
+Tato vlastnost je velmi důležitá v optimalizaci – nemusíme hledat celé globální optimum, stačí najít lokální a víme, že je to ono.
+==== Hledání extrémů ====
+Najít extrém neznamená jen najít hodnotu funkce, ale určit i bod, kde se nachází, a typ extrému.
+  * **Volné extrémy**: použijeme **podmínku nulového gradientu** a **Hessovu matici** pro test typu extrému.
+  * **Vázané extrémy**: použijeme **Lagrangeovy multiplikátory**.
+==== Příklady ====
+. **Volný extrém:**
+  * Např. funkce %%<mjax>f(x, y) = x^2 + y^2</mjax>%%
+  * má globální minimum v bodě %%<mjax>x^* = (0, 0),\quad f(x^*) = 0</mjax>%%
+  * Jde o tvar trychtýře – minimum je ve středu a zároveň lokální i globální.
+. **Vázaný extrém:**
+  * Minimalizujeme %%<mjax>f(x, y) = x^2 + y^2</mjax>%%
+  * za podmínky %%<mjax>x + y = 1</mjax>%%
+  * Extrém se hledá pouze na přímce, ne na celé rovině.
+Takové úlohy se řeší metodou **Lagrangeových multiplikátorů**, která převede problém s omezením na rovnici, kterou můžeme řešit pomocí derivací.
+==== Dělení extrémů podle kontextu ====
+| Typ extrému   | Omezení            | Podmínky hledání       |
+|---------------|--------------------|-------------------------|
+| Volný         | žádné              | derivace = 0            |
+| Vázaný        | rovnosti / nerovnosti | Lagrange, KKT podmínky  |
+| Globální      | celé D             | extrém celé množiny     |
+| Lokální       | okolí bodu         | extrém v nějaké kouli   |
+===== 5. Volné lokální extrémy diferencovatelných funkcí =====
+Zde hledáme extrémy hladkých funkcí \( f:\mathbb{R}^n \to \mathbb{R} \) **bez omezení** – tedy volné extrémy uvnitř definičního oboru.
+=== Podmínka 1. řádu ===
+Stacionární bod \( x^* \) je kandidát na extrém, pokud platí:
+%%<mjax>\nabla f(x^*) = 0</mjax>%%
+<abbr title="Gradient v bodě x^* musí zmizet – žádný směr, kterým se hodnota f mění.">❓</abbr>
+To znamená, že funkce nemá v tomto bodě žádný směr, kterým by mohla růst nebo klesat – ležíme v „rovnovážné poloze“.
+=== Podmínka 2. řádu ===
+Pro rozhodnutí typu stacionárního bodu, zda jde o minimum, maximum nebo sedlový bod, použijeme **Hessovu matici** \( H_f(x) \) – matici druhých derivací.
+  * Pokud je \( H \succ 0 \), jedná se o ostré lokální minimum.
+  * Pokud je \( H \succeq 0 \), jde o minimum, které ale nemusí být ostré.
+  * Pokud je \( H \prec 0 \), máme ostré lokální maximum.
+  * Pokud je \( H \preceq 0 \), jde o maximum, které nemusí být ostré.
+  * Pokud je Hessova matice indefinitní, jedná se o sedlový bod – tedy žádný extrém.
+Tato klasifikace vychází z tvaru funkce v okolí bodu – pomocí křivosti poznáme, zda se funkce chová jako dno mísy, vrchol kopce nebo sedlo.
+==== Numerické metody ====
+Když analyticky nelze najít řešení, použijeme **iterační metody** – postupně se přibližujeme k optimu:
+  * **Obecná iterace:**
+    * Volíme počáteční bod \(x_0\), směr \(v_k\) a krok \(\alpha_k > 0\)
+    * Iterace:  %%<mjax>x_{k+1} = x_k + \alpha_k v_k</mjax>%%
+    * Směr \(v_k\) je **sestupný**, pokud:  %%<mjax>\nabla f(x_k)^T v_k < 0</mjax>%%
+  * V každém kroku tedy jdeme směrem, který zaručeně zmenšuje hodnotu funkce – tím se přibližujeme k minimu.
+  * **Gradientní metoda (největší spád):**
+    * Směr je záporný gradient:  %%<mjax>x_{k+1} = x_k - \alpha_k \nabla f(x_k)</mjax>%%
+    * Jednoduchá, ale může **konvergovat pomalu** nebo klesat příliš „cikcak“ → závisí na volbě kroku.
+  * Jde o nejjednodušší metodu: jdeme „dolů z kopce“ po nejstrmější cestě, ale bez přizpůsobení křivosti terénu.
+  * **Newtonova metoda:**
+    * Zohledňuje zakřivení funkce pomocí Hessovy matice:  %%<mjax>x_{k+1} = x_k - H_f(x_k)^{-1} \nabla f(x_k)</mjax>%%
+    * Rychlá (kvadratická) konvergence, ale výpočetně náročná – vyžaduje inverzi Hessovy matice.
+  * Funguje dobře, pokud máme „dobrý start“ a funkce je pěkně zakřivená – jinak může selhat.
+  * **Gauss-Newtonova metoda:**
+    * Vhodná pro funkce, které jsou kvadrátem vektorové funkce \( f(x) = \|g(x)\|_2^2 \)
+    * Iterace:  %%<mjax>x_{k+1} = x_k - \left(J^T J\right)^{-1} J^T g(x_k)</mjax>%%
+    * kde \( J \) je Jacobiho matice funkce \( g(x) \)
+  * Gauss-Newton je zjednodušená verze Newtonovy metody, která používá jen první derivace.
+  * **Levenberg-Marquardtova metoda:**
+    * Kombinuje robustnost gradientní metody s rychlostí Gauss-Newtonovy
+    * Iterace:  %%<mjax>x_{k+1} = x_k - \left(J^T J + \mu I\right)^{-1} J^T g(x_k)</mjax>%%
+    * Parametr \( \mu > 0 \) umožňuje plynule přecházet mezi oběma metodami
+  * Pokud Gauss-Newton selhává, přidáme regularizační člen \( \mu I \), čímž omezíme „skoky“ v citlivých oblastech – metoda se chová stabilněji.
+===== 6. Lokální extrémy diferencovatelných funkcí vázané rovnostmi =====
+Pokud hledáme extrém funkce \( f(x) \) za podmínky, že proměnné \( x \in \mathbb{R}^n \) musí splňovat rovnosti \( g_i(x) = 0 \), musíme vzít v úvahu nejen chování samotné funkce, ale i **omezení**, která určují přípustné body.
+Taková úloha má tvar:
+%%<mjax>\min f(x)\quad \text{za podmínky}\quad g_1(x) = 0,\,\dots,\,g_m(x) = 0</mjax>%%
+Tyto rovnosti určují množinu povolených řešení – tzv. **povrch**. Extrém hledáme **na tomto povrchu**, tedy jen mezi body, které splňují dané podmínky.
+=== Podmínka prvního řádu – Lagrangeovy multiplikátory ===
+Podmínky řešíme pomocí **Lagrangeovy funkce**:
+%%<mjax>\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)</mjax>%%
+<abbr title="Spojuje funkci a omezení do jediné funkce, jejíž stacionární body dávají kandidáty na extrém.">❓</abbr>
+Bod \( x^* \in \mathbb{R}^n \) je kandidátem na extrém, pokud existuje vektor multiplikátorů \( \lambda = (\lambda_1,\dots,\lambda_m) \), takový že:
+  * %%<mjax>\nabla_x \mathcal{L}(x^*, \lambda) = \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) = 0</mjax>%%
+  * %%<mjax>g_i(x^*) = 0\quad \text{pro všechna } i = 1,\dots,m</mjax>%%
+Tato podmínka říká, že v bodě \( x^* \) je gradient funkce \( f \) lineární kombinací gradientů omezení \( g_i \) – tedy **ležící v ortogonálním doplňku tečného prostoru**.
+Jinými slovy: v optimu se nelze „vydat směrem“ uvnitř množiny bez toho, aby se zvyšovala hodnota funkce.
+=== Geometrická interpretace ===
+Tečný prostor k množině \( \{x \mid g(x) = 0\} \) v bodě \( x^* \) je tvořen vektory \( v \), pro které platí: %%<mjax>g'(x^*) v = 0</mjax>%%
+– tedy množinou vektorů kolmých na gradienty omezení.
+Gradient funkce \( f \) musí ležet ve směru normály, tj. být kombinací \(\nabla g_i\).
+=== Druhý řád – určení typu extrému ===
+Hessovu matici Lagrangeovy funkce vzhledem k \( x \) označme:
+%%<mjax>H(x, \lambda) = \nabla^2_{xx} \mathcal{L}(x, \lambda)</mjax>%%
+Pro rozhodnutí o typu extrému:
+  * Zkoumáme **zrestrikovaný Hessian** na tečný prostor množiny \( \{g_i(x)=0\} \),
+  * Pokud je pozitivně definitní, jde o **lokální minimum**,
+  * Pokud negativně definitní, jde o **lokální maximum**,
+  * Pokud není ani jedno – **sedlový bod**.
+=== Kontrola hranic množiny ===
+Pokud množina \( D \), na které optimalizujeme, má i ohraničení, musíme kromě stacionárních bodů vyšetřit i **hranici domény** – extrém může vzniknout právě tam, i když nevyhoví podmínce \( \nabla_x \mathcal{L} = 0 \).
+To zahrnuje:
+  * krajní body množiny,
+  * místa, kde se gradienty omezení stávají lineárně závislými,
+  * a další situace, kdy už neplatí standardní podmínky.
+=== Postup ===
+  - Sestavíme Lagrangeovu funkci \( \mathcal{L}(x,\lambda) = f(x) + \lambda^T g(x) \).
+  - Najdeme kandidátní body \( (x^*, \lambda^*) \), které splňují:
+    * \( \nabla_x \mathcal{L}(x^*, \lambda^*) = 0 \)
+    * \( g_i(x^*) = 0 \)
+  - Zkontrolujeme druhý řád – restrikci Hessovy matice.
+  - Pokud je doména omezená, zkontrolujeme i hraniční body.
+  - Vybereme bod s nejlepší hodnotou \( f(x^*) \).
+=== Aplikace ===
+Lagrangeovy multiplikátory umožňují řešit mnoho praktických úloh:
+  * minimalizace nákladů při daných zdrojích,
+  * optimalizace návrhů pod strukturálními podmínkami,
+  * nalezení extrému na parametrické křivce nebo ploše,
+  * ekonomické rovnováhy s rozpočtovým omezením.
+===== 7. Úloha lineárního programování (LP) =====
-Lineární programování (LP) je optimalizační disciplína, ve které hledáme vektor \(x\in\mathbb{R}^n\), který minimalizuje (nebo maximalizuje) lineární cílovou funkci za předpokladu, že \(x\) splňuje soustavu lineárních omezení (nerovnic nebo rovnic).
+Lineární programování (LP) je metoda pro **optimalizaci lineární funkce** při **lineárních omezeních**. Typicky hledáme maximum nebo minimum nějakého cíle (např. zisku, výkonu) za omezených podmínek (rozpočet, kapacita, suroviny apod.)
 === Úvod k teorii lineárního programování, geometrický význam===
 Lineární programování (LP) pracuje s lineární cílovou funkcí
-%%<mjax>z = c^{T}x</mjax>%%
+%%<mjax>z = c^{T}x</mjax>%% <abbr title="Minimalizujeme lineární funkci cᵀx při lineárních omezeních na x.">❓</abbr>
-a konvexním polyedrem definovaným lineárními omezeními (rovnicemi či nerovnicemi). Hlavními body teorie jsou:
+a konvexním polyedrem definovaným lineárními omezeními (rovnicemi či nerovnicemi).
+Hlavními body teorie jsou:
   * **Konvexní polyedr a vrcholy**
-  Soubor všech \(x\) splňujících
+    * soubor všech \(x\) splňujících %%<mjax>A\,x \ge b,\;x \ge 0</mjax>%%
-%%<mjax>A\,x \ge b,\;x \ge 0</mjax>%%
+    * tvoří konvexní množinu (polyedr). Každý takový polyedr lze popsat buď jako průnik poloprostorů, nebo jako konvexní obal (konvexní kombinace) svých extrémních bodů (vrcholů) a hran (hranové body).
-  tvoří konvexní množinu (polyedr). Každý takový polyedr lze popsat buď jako průnik poloprostorů, nebo jako konvexní obal (konvexní kombinace) svých extrémních bodů (vrcholů) a hran (hranové body).
+    * = Řešení soustavy omezení \( A x \le b \) tvoří konvexní oblast v prostoru.
   * **Vrcholy (extermální body)**
-  Vrcholem (extrémním bodem) polyedru rozumíme bod, který nelze vyjádřit jako konvexní kombinaci dvou jiných bodů v polyedru. Algebraicky to odpovídá základnímu (basic) řešení:
+    * vrcholem (extrémním bodem) polyedru rozumíme bod, který nelze vyjádřit jako konvexní kombinaci dvou jiných bodů v polyedru. Algebraicky to odpovídá základnímu (basic) řešení:
-  - Pokud máme \(m\) lineárních rovnic (po úpravě do standardního tvaru) a \(n\) proměnných, každý vrchol odpovídá výběru \(m\) nezávislých (bázových) proměnných, ostatní se nastaví na nulu.
+      * Pokud máme \(m\) lineárních rovnic (po úpravě do standardního tvaru) a \(n\) proměnných, každý vrchol odpovídá výběru \(m\) nezávislých (bázových) proměnných, ostatní se nastaví na nulu.
+    * = Body, které nelze napsat jako průměr jiných bodů v oblasti – právě v těchto bodech může ležet optimum.
   * **Optimum leží ve vrcholu**
-  Vzhledem k tomu, že
+    * vzhledem k tomu, že %%<mjax>z = c^{T}x</mjax>%%
-%%<mjax>z = c^{T}x</mjax>%%
+    * je lineární, musí globální optimum (minimální či maximální hodnota) na konvexním polyedru nastat alespoň v jednom vrcholu. Jinými slovy, pro LP není třeba zkoumat vnitřek polyedru: stačí prohledat vrcholy (popř. hrany mezi dvěma vrcholy, pokud existuje více optimálních vrcholů).
-je lineární, musí globální optimum (minimální či maximální hodnota) na konvexním polyedru nastat alespoň v jednom vrcholu. Jinými slovy, pro LP není třeba zkoumat vnitřek polyedru: stačí prohledat vrcholy (popř. hrany mezi dvěma vrcholy, pokud existuje více optimálních vrcholů).
+    * = Pokud má LP optimum, pak existuje alespoň v jednom z vrcholů této oblasti. Nemusíme tedy prohledávat celý prostor, stačí kontrolovat vrcholy.
   * **Více optimálních vrcholů (degenerace)**
-Pokud existují dva vrcholy \(x^{(1)}, x^{(2)}\) s
+    * Pokud existují dva vrcholy \(x^{(1)}, x^{(2)}\) s %%<mjax>c^{T}x^{(1)} = c^{T}x^{(2)} = z^{*},</mjax>%%
-%%<mjax>c^{T}x^{(1)} = c^{T}x^{(2)} = z^{*},</mjax>%%
+    * pak každá konvexní kombinace %%<mjax>x = \alpha\,x^{(1)} + (1-\alpha)\,x^{(2)},\quad 0\le\alpha\le1,</mjax>%%
-pak každá konvexní kombinace
+    * je také optimální a leží na hraně spojující tyto dva vrcholy. To znamená, že optimální množina může být celá hrana (nejen izolovaný vrchol).
-%%<mjax>x = \alpha\,x^{(1)} + (1-\alpha)\,x^{(2)},\quad 0\le\alpha\le1,</mjax>%%
+    * = Pokud má více vrcholů stejnou hodnotu cílové funkce, optimum je libovolná jejich kombinace – tedy i celé hrany mezi nimi.
-je také optimální a leží na hraně spojující tyto dva vrcholy. To znamená, že optimální množina může být celá hrana (nejen izolovaný vrchol).
   * **Geometrické důsledky**
-  - Pokud polyedr nemá žádné vrcholy (např. neomezená směrově čtvercová množina), může optimum neexistovat (např. LP cílová funkce neklesá) nebo být dosaženo jen „v nekonečnu“.
+    - Pokud polyedr nemá žádné vrcholy (např. neomezená směrově čtvercová množina), může optimum neexistovat (např. LP cílová funkce neklesá) nebo být dosaženo jen „v nekonečnu“.
-  - Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.
+    - Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.
 === Základní tvar LP ===
 Obecná formulace (kanonický tvar v „nerovnicích“) je:
@@ Line 492: / Line 624: @@
 Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav:
-. **Přidání nezáporných slack proměnných**
+. **Přidání nezáporných slack proměnných** (nerovností na rovnosti)
-   Pro každé omezení ve tvaru nerovnosti (např. \(a_{i}^{T}x \le b_{i}\)) přidáme novou proměnnou \(u_{i} \ge 0\), aby vznikla rovnice
+  * Pro každé omezení ve tvaru nerovnosti (např. \(a_{i}^{T}x \le b_{i}\)) přidáme novou proměnnou \(u_{i} \ge 0\), aby vznikla rovnice %%<mjax>a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.</mjax>%%
-%%<mjax>a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.</mjax>%%
+. **Vyjádření neomezených reálných proměnných** (převedení volných proměnných)
+  * Každou proměnnou bez znaménkového omezení rozložíme jako rozdíl dvou nezáporných: %%<mjax>x_j = x_j^+ - x_j^-,\quad x_j^+,\,x_j^- \ge 0</mjax>%%
+==== Varianty zadání ====
+Úlohu LP lze převádět mezi různými tvary – např. aby vyhovovala algoritmům (simplex, metoda vnitřního bodu) nebo vizualizaci.
+  * **Minimalizace vs. maximalizace:**
+    * Maximalizaci převedeme na minimalizaci změnou znaménka: %%<mjax>\max c^T x \equiv \min (-c)^T x</mjax>%%
+  * **Rovnosti a nerovnosti:**
+    * Rovnost převedeme na dvě opačné nerovnosti: %%<mjax>a^T x = b \equiv a^T x \le b \ \text{a} \ -a^T x \le -b</mjax>%%
+  * **Proměnné bez znaménka:**
+    * Volná proměnná se nahradí rozdílem dvou nezáporných: %%<mjax>x_i = x_i^+ - x_i^-,\quad x_i^+, x_i^- \ge 0</mjax>%%
+  * **Slack proměnné (u nerovností):**
+    * Každou nerovnost \(a_i^T x \le b_i\) převedeme na rovnici přidáním nové nezáporné proměnné: %%<mjax>a_i^T x + s_i = b_i,\quad s_i \ge 0</mjax>%%
-. **Vyjádření neomezených reálných proměnných**
+Tím dostaneme **kanonický tvar LP** – s rovnicemi a nezápornými proměnnými, se kterým umí pracovat všechny běžné algoritmy.
-   Každou proměnnou \(x_{j}\), která nemá nenegativní omezení, zapíšeme jako rozdíl dvou nezáporných proměnných:
-%%<mjax>x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+} \ge 0,\; x_{j}^{-} \ge 0.</mjax>%%
-=== Převod LP do kanonického tvaru (stručně) ===
+==== Převod LP do kanonického tvaru ====
 **Původní úloha (max):**
@@ Line 526: / Line 675: @@
 \]
 === Typické použití LP ===
-LP se uplatňuje v mnoha oblastech, například:
-  * **Plánování výroby a alokace zdrojů** – maximalizace zisku z produktů nebo minimalizace výrobních nákladů, kde \(x_j\) jsou počty vyrobených jednotek, \(A\,x \le b\) zachycuje omezení surovin, kapacit, pracovních hodin.
-  * **Směrování a toky v síti** – minimalizace nákladů na přepravu z bodu A do B s omezeními kapacit hran; LP formulace pro \emph{min-cost flow}.
-  * **Optimalizace transportních problémů (assignment, transporte, dietă)** – přiřazení zaměstnanců úkolům, sklady-prodejny-dodávky, minimální náklady na dietní plán.
-=== Přibližné řešení přeurčených soustav ===
+Lineární programování se používá v různých oborech, kde je třeba nalézt nejlepší možné řešení za daných podmínek:
-Uvažujme přeurčenou soustavu lineárních rovnic \(A\,x \approx b\), kde \(A\in\mathbb{R}^{m\times n}\), \(m>n\). Místo klasického minimaxu v L₂-normě (least squares) můžeme hledat řešení, které minimalizuje odchylku v jiných normách – L₁ resp. L∞. Obě formulace lze přepsat jako LP.
-=== L∞-norm (max-norm) ===
+  * **Plánování výroby a alokace zdrojů**
-Chceme minimalizovat největší odchylku:
+    * Např. maximalizace zisku z produktů nebo minimalizace nákladů.
-%%<mjax>
+    * Omezující podmínky mohou být kapacity strojů, pracovní doba, množství surovin apod.
-\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{\infty}
+  * **Směrování a toky v síti**
-\;=\;\min_{x}\; \max_{i=1\dots m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|.
+    * Minimalizace nákladů na přepravu v dopravní síti.
-</mjax>%%
+    * Omezení tvoří kapacity hran a požadavky na vstup/výstup v uzlech.
-Formulujeme ekvivalentně:
+  * **Transportní a přiřazovací problémy**
-%%<mjax>
+    * Např. optimální distribuce zboží ze skladů do prodejen.
-\min_{x,\;t}\; t
+    * Přiřazování pracovníků k úkolům nebo trasám.
-\quad\text{za podmínek}\quad
+  * **Dietní problém**
--\,t \;\le\; a_{i}^{T}x - b_{i}\;\le\; t,\quad i=1,\dots,m,\quad t\in\mathbb{R}.
+    * Hledání nejlevnější kombinace potravin splňující výživové normy.
-</mjax>%%
+    * Každá potravina má známé nutriční složení a cenu.
+  * **Ekonomické rovnováhy a plánování**
+    * Například v makroekonomii při modelování rovnováh v sektorech nebo při investičním plánování.
+LP slouží jako základ pro složitější varianty – např. celočíselné, nelineární nebo stochastické programování.
+==== Přibližné řešení přeurčené soustavy ====
+Přeurčená soustava rovnic \( A x = b \), kde počet rovnic \( m \) převyšuje počet neznámých \( n \), obvykle nemá přesné řešení. Hledáme proto takové \( x \), které dává nejlepší možné přiblížení – tj. minimalizuje odchylku \( A x - b \) podle zvolené normy.
+Typické volby:
+  * **1-norma (součet absolutních odchylek):**
+    * %%<mjax>\min \|A x - b\|_1 = \sum_{i=1}^m |a_i^T x - b_i|</mjax>%% <abbr title="Robustní vůči odlehlým hodnotám – penalizuje každou chybu stejně.">❓</abbr>
+  * **∞-norma (maximální odchylka):**
+    * %%<mjax>\min \|A x - b\|_\infty = \max_{i=1,\dots,m} |a_i^T x - b_i|</mjax>%% <abbr title="Zajišťuje, že žádná rovnice není výrazně porušena – důležité při rovnoměrných požadavcích.">❓</abbr>
+Obě tyto úlohy lze převést na lineární programování (LP) zavedením pomocných proměnných a vhodných lineárních omezení.
+== L∞-norm (max-norm) ==
+  * Chceme minimalizovat největší odchylku: %%<mjax> \min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{\infty} \;=\;\min_{x}\; \max_{i=1\dots m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|. </mjax>%%
+  * Formulujeme ekvivalentně: %%<mjax> \min_{x,\;t}\; t \quad\text{za podmínek}\quad -\,t \;\le\; a_{i}^{T}x - b_{i}\;\le\; t,\quad i=1,\dots,m,\quad t\in\mathbb{R}.</mjax>%%
 Výsledkem je LP v proměnných \((x_1,\dots,x_n,t)\). Optimální \(x^{*}\) minimalizuje největší reziduum.
-=== L₁-norm (taxicab-norma) ===
+== L₁-norm (taxicab-norma) ==
-Chceme minimalizovat součet absolutních odchylek:
+  * Chceme minimalizovat součet absolutních odchylek: %%<mjax>\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{1}\;=\;\min_{x}\;\sum_{i=1}^{m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|.</mjax>%%
-%%<mjax>
+  * Formulujeme ekvivalentně:%%<mjax>\min_{x,\;\{u_{i}\}}\;\sum_{i=1}^{m}u_{i}\quad\text{za podmínek}\quad-\,u_{i} \;\le\; a_{i}^{T}x - b_{i}\;\le\; u_{i},\quad u_{i}\;\ge\; 0,\;i=1,\dots,m.</mjax>%%
-\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{1}
+  * Nalezené \(\{u_{i}^{*}\}\) jsou pak absolutní odchylky a \(\sum_i u_i^*\) je minimální součet.
-\;=\;\min_{x}\;\sum_{i=1}^{m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|.
-</mjax>%%
-Formulujeme ekvivalentně:
-%%<mjax>
-\min_{x,\;\{u_{i}\}}\;\sum_{i=1}^{m}u_{i}
-\quad\text{za podmínek}\quad
--\,u_{i} \;\le\; a_{i}^{T}x - b_{i}\;\le\; u_{i},\quad
-u_{i}\;\ge\; 0,\;i=1,\dots,m.
-</mjax>%%
-Nalezené \(\{u_{i}^{*}\}\) jsou pak absolutní odchylky a \(\sum_i u_i^*\) je minimální součet.
 === Kompletní příklad přeurčené soustavy v L₁ a L∞ ===
@@ Line 661: / Line 817: @@
 === Řešení lineárního programu (stručně) ===
-Po převedení LP do kanonického (rovnicového) tvaru
+Po převedení LP do kanonického (rovnicového) tvaru %%<mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax>%%
-%%<mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax>%%
-věnujeme pozornost následujícím možnostem:
+řešíme optimalizační úlohu nad konvexní množinou řešení (polyedrem). Existuje několik přístupů:
   * **Vyhledání vrcholů a porovnání cílové funkce**
-  - Najdeme všechny vrcholy jako soustavu lineárních rovnic pro každou dvojici omezení a prohlásíme za optimum vrchol s maximální hodnotou.
+    * Všechny vrcholy polyedru odpovídají základním řešením soustavy \(A x = b\), kde \(x \ge 0\).
-  - **výhoda:** pro malé problémy ve 2D(3D) lze řešit graficky.
+    * Pro malé problémy (2D, 3D) lze vrcholy zjistit graficky jako průsečíky omezení.
-  - **Nevýhoda:** Počet vrcholů roste exponenciálně (\(\binom{n}{m}\)), takže postup je vhodný pouze pro velmi malé rozměry.
+    * Vyhodnotíme hodnotu cílové funkce \(c^T x\) ve všech vrcholech a zvolíme nejlepší.
+    * **Výhoda:** Přehledná geometrická interpretace, vhodná pro ilustraci.
+    * **Nevýhoda:** Počet vrcholů může být exponenciální (\(\binom{n}{m}\)), což je výpočetně neúnosné pro větší úlohy.
   * **Simplexová metoda (pohyb po hranách polyedru)**
-  - Namísto úplného výčtu vrcholů se pohybujeme z vrcholu na sousední vrchol, kde se hodnota cílové funkce vždy zlepšuje.
+    * Nehledáme všechny vrcholy – postupně se přesouváme z jednoho vrcholu k sousednímu, přičemž hodnota cílové funkce se zlepšuje (klesá nebo roste).
-  - Metoda prakticky najde optimální řešení ve velmi malém počtu kroků pro většinu reálných LP.
+    * V každém kroku vybíráme bázové proměnné a aktualizujeme tzv. simplexovou tabulku.
-  - **Výhoda:** Efektivní
+    * Algoritmus konverguje k optimu v konečně mnoha krocích, pokud nenastane degenerace.
-  - **Nevýhoda:** Může se zacyklit
+    * **Výhoda:** Prakticky velmi rychlý pro většinu úloh – často jen málo kroků.
+    * **Nevýhoda:** V krajních případech může cyklit (řeší se např. Blandovým pravidlem).
+===== 8. Geometrie LP =====
+Geometrie lineárního programování je založena na vlastnostech **konvexních množin** a **mnohostěnů (polyedrů)**. LP úloha se řeší hledáním extrému lineární funkce na takové množině.
+==== Konvexní množiny ====
+  * Množina \(C \subseteq \mathbb{R}^n\) je **konvexní**, pokud pro každé dva body \(x, y \in C\) a libovolné \(\lambda \in [0,1]\) platí: %%<mjax>\lambda x + (1-\lambda)y \in C</mjax>%%<abbr title="Úsečka mezi každými dvěma body leží celá v množině – žádné 'díry' nebo 'záhyby'.">❓</abbr>
+  * Ekvivalentně: obsahuje všechny **konvexní kombinace** svých bodů, tedy výrazy ve tvaru: %%<mjax>x = \sum_{i=1}^{k} \alpha_i x_i,\quad \alpha_i \ge 0,\quad \sum \alpha_i = 1</mjax>%%<abbr title="Konvexní kombinace je lineární kombinace s nezápornými váhami, které dávají dohromady 1.">❓</abbr>
+  * Konvexní množiny jsou důležité, protože:
+    * minimum lineární funkce na konvexní množině je dosaženo na hranici (nejčastěji ve vrcholu),
+    * každé lokální minimum je zároveň globální.
+==== Polyedr (konvexní mnohostěn) ====
+  * **Polyedr** je průnik konečně mnoha poloprostorů, tedy množina řešení lineárních nerovnic: %%<mjax>P = \{x \in \mathbb{R}^n \mid A x \ge b\}</mjax>%%<abbr title="Obecná definice provázaná s LP – oblast omezení tvoří polyedr.">❓</abbr>
+  * Je vždy konvexní, ale nemusí být omezený (např. otevřený klín nebo nekonečný paprsek).
+    * Pokud polyedr **neobsahuje přímku**, má extrémní body – lze tedy hledat optimum.
+    * Pokud obsahuje přímku, minimum lineární funkce často neexistuje nebo je dosaženo „v nekonečnu“.
+  * Každý polyedr má:
+    * **vrcholy (extrémní body)** – body, které nelze vyjádřit jako konvexní kombinace jiných bodů množiny,
+    * **hrany, fasety, stěny** – tj. geometrické části různých dimenzí:
+      * 0D – vrchol,
+      * 1D – hrana,
+      * \(n{-}1\)D – faseta.
+==== Extrémní body ====
+  * Bod \(x \in P\) je **extrémní bod** (vrchol), pokud neexistují dva různé body \(x_1, x_2 \in P\), že: %%<mjax>x = \lambda x_1 + (1-\lambda) x_2,\quad \lambda \in (0,1)</mjax>%%<abbr title="Vrcholy nelze 'rozložit' – právě v nich leží optimum lineární funkce.">❓</abbr>
+  * Algebraicky odpovídají **základním řešením** soustavy rovnic.
+    * Extrémní body existují právě tehdy, když množina řešení neobsahuje přímku.
+  * V LP se optimální řešení (pokud existuje) nachází vždy v některém extrémním bodě polyedru přípustných řešení.
+    * Minimum lineární funkce na konvexním polyedru je dosaženo na **stěně**, kde má funkce stejnou hodnotu.
+    * Tato stěna je průnik s tzv. **opěrnou nadrovinou**:  %%<mjax>H = \{x \in \mathbb{R}^n \mid c^T x = c^T x^*\}</mjax>%% <abbr title="Hyperrovina, ve které je dosaženo minima – 'dotýká se' množiny.">❓</abbr>
+===== 9. Dualita v LP =====
+Každé úloze lineárního programování (tzv. **primární úloze**) odpovídá jiná LP úloha – tzv. **duální úloha**. Obě spolu souvisí: řešení jedné poskytuje informace o řešení druhé a zároveň může sloužit jako nástroj pro jednodušší nalezení optima.
+==== Primární a duální úloha ====
+Nechť máme primární úlohu ve tvaru: %%<mjax>\min\{\,c^T x \mid A x \ge b,\; x \ge 0\,\}</mjax>%%
+K ní přísluší duální úloha: %%<mjax>\max\{\,b^T y \mid A^T y \le c,\; y \ge 0\,\}</mjax>%%
+  * Vektory \(x\) a \(y\) jsou proměnné v primární a duální úloze.
+  * Matice a vektory jsou převrácené – omezení primalu se stávají cílovou funkcí dualu a naopak.
+  * Duální úloha je tzv. **reverzibilní úprava** primární – přechod mezi nimi je čistě formální.
+==== Slabá dualita ====
+  * **Věta o slabé dualitě:**
+    * Pro každé přípustné řešení \(x\) primární úlohy a každé přípustné \(y\) duální úlohy platí: %%<mjax>c^T x \ge b^T y</mjax>%%<abbr title="Cílová funkce primalu je vždy větší nebo rovna cíli dualu.">❓</abbr>
+    * Duální hodnota je tedy **dolní mez** primalu.
+  * Pokud se stane, že: %%<mjax>c^T x = b^T y</mjax>%%
+    * pro nějaké přípustné dvojice \((x^*, y^*)\), pak jsou **obě řešení optimální**.
+==== Silná dualita ====
+  * **Věta o silné dualitě:**
+    * Pokud má primární úloha nebo duální úloha **optimální řešení**, pak:
+      * druhá úloha má také řešení,
+      * a platí: %%<mjax>c^T x^* = b^T y^*</mjax>%%<abbr title="Optimální hodnoty cílové funkce se rovnají.">❓</abbr>
+  * Tato rovnost se označuje jako **certifikát optimality** – potvrzuje, že nalezené řešení je opravdu optimum.
+  * Ekvivalentně platí:
+    * Primal má optimum ⇔ dual má optimum ⇔ hodnoty jsou stejné.
+==== Komplementarita ====
+  * **Komplementární podmínky:**
+    * Jsou splněny právě tehdy, když jsou obě řešení optimální:
+      * Pro každé \(i\): %%<mjax>x_i > 0 \;\Rightarrow\; (A^T y)_i = c_i</mjax>%%
+      * Pro každé \(j\): %%<mjax>y_j > 0 \;\Rightarrow\; (A x)_j = b_j</mjax>%%
+      * Obecně: %%<mjax>(c_i - (A^T y)_i) \cdot x_i = 0,\quad ((A x)_j - b_j) \cdot y_j = 0</mjax>%%<abbr title="Každý člen buď aktivně omezuje, nebo má nulový dopad.">❓</abbr>
+  * Jinými slovy: **každá podmínka buď svazuje řešení (aktivní), nebo má nulový stínový dopad**.
+==== Význam a využití ====
+  * Dualita v LP umožňuje:
+    * jednodušší konstrukci algoritmů (např. dual simplex),
+    * odhad kvality řešení primalu pomocí dualu (dolní/vrchní meze),
+    * výpočet **stínových cen** – jak moc se zlepší optimum, když uvolníme omezení,
+    * rozhodování o významu jednotlivých omezení a jejich dopadu na výsledek.
+  * V praxi se primal a duální řešení často hledají současně – např. v simplexové metodě se během výpočtu tvoří i informace o duálu.
+===== 10. Konvexní funkce a konvexní optimalizace =====
+Konvexní funkce tvoří základ moderní optimalizace – mají příznivé geometrické i analytické vlastnosti. Hledání minima konvexní funkce je jednodušší, protože **každé lokální minimum je zároveň globální minimum**.
+==== Definice konvexní funkce ====
+  * Funkce \( f: \mathbb{R}^n \to \mathbb{R} \) je **konvexní**, pokud pro každé \( x, y \in \mathbb{R}^n \) a každé \( \lambda \in [0,1] \) platí: %%<mjax>f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda) f(y)</mjax>%% <abbr title="Hodnota v bodě mezi x a y není větší než průměr hodnot v x a y – tedy 'pod obloukem'.">❓</abbr>
+  * Funkce je **striktně konvexní**, pokud nerovnost je ostrá pro \(x \ne y\).
+  * Konvexita znamená, že graf funkce je „ohnutý směrem nahoru“.
+==== Epigraf a subkontura ====
+  * **Epigraf** funkce \( f \): množina bodů nad grafem: %%<mjax>\mathrm{epi}(f) = \{ (x,t) \in \mathbb{R}^n \times \mathbb{R} \mid f(x) \le t \}</mjax>%% <abbr title="Epigraf je objem podložený funkcí – konvexní funkce má konvexní epigraf.">❓</abbr>
+  * **Subkontura (sublevel množina)** – množina všech bodů, kde funkce nepřesahuje danou hodnotu: %%<mjax>\{x \in \mathbb{R}^n \mid f(x) \le \alpha \}</mjax>%% <abbr title="Zobrazujeme oblasti, kde je funkce pod určitou hladinou.">❓</abbr>
+==== Podmínky konvexity podle derivací ====
+Pokud je \(f\) diferencovatelná:
+  * **1. derivace – gradientová podmínka:** Funkce \(f\) je konvexní ⇔ platí: %%<mjax>f(y) \ge f(x) + \nabla f(x)^T (y - x)</mjax>%% <abbr title="Dotyková rovina funkci nepodsekává – funkce leží vždy nad tečnou.">❓</abbr>
+Pokud je \(f\) dvakrát diferencovatelná:
+  * **2. derivace – Hessova podmínka:** Funkce \(f\) je konvexní ⇔ její Hessova matice je pozitivně semidefinitní: %%<mjax>\nabla^2 f(x) \succeq 0\quad \text{(pro všechna } x)</mjax>%% <abbr title="Funkce je konvexní, pokud její křivost (druhé derivace) nejsou záporné.">❓</abbr>
+==== Úloha konvexní optimalizace ====
+  * Obecná úloha konvexní optimalizace má tvar: %%<mjax>\min f(x) \quad \text{za podmínek } x \in C</mjax>%%
+  * kde:
+    * \( f: \mathbb{R}^n \to \mathbb{R} \) je konvexní funkce,
+    * \( C \subseteq \mathbb{R}^n \) je konvexní množina (např. množina omezení).
+  * Důležité vlastnosti:
+    * Pokud je funkce i množina omezení konvexní ⇒ **každé lokální minimum je globální**.
+    * Existují efektivní algoritmy (např. metoda vnitřního bodu, subgradienty, CVX solvery).
+  * Typické aplikace:
+    * Optimalizace ztrátové funkce v machine learningu (ridge, LASSO),
+    * Portfolio management (mean-variance model),
+    * Řízení systémů a model prediktivního řízení (MPC),
+    * Design sítí, rozpočtové plánování.
-===== Dualita v LP =====
-===== Konvexní funkce ======

Trace: • b4b33alg

Differences

Search

Navigation

Print/export

Tools

QR Code