The wiki page is under active construction, expect bugs.

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b0b33opt [2025/06/04 15:17] – [Optimální proložení bodů podprostorem (PCA)] zapleka3statnice:bakalar:b0b33opt [2025/06/12 10:33] (current) – [Podmínky konvexity podle derivací] el_dusto
Line 1: Line 1:
-==== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita. ====+====== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programová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]] [[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 390: Line 390:
  
  
----------------+===== 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.
  
-**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.+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ů.
  
-PCA lze chápat dvojím způsobem:+==== Definice ====
  
-**1. Minimální vzdálenost od podprostoru:** +Mějme funkci \( f: D \subset \mathbb{R}^n \rightarrow \mathbb{R} \).
-   +
-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):**  +  * **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>%%
  
-Volíme \(X\) tak, aby projekce dat na podprostor měla co největší celkový rozptyl, tj.   +Lokální extrém je jen „nejlepší v okolí“, zatímco globální je nejlepší **v celé množině**.
-%%<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>+
  
-=== Funkce stopa (trace) ===+==== Kdy je extrém globální ====
  
-Stopa matice \(A\in\mathbb{R}^{n\times n}\) je součet jejích diagonálních prvků:+Pokud je funkce **konvexní**, pak **každé lokální minimum je zároveň globální minimum**. U konkávních funkcí analogicky pro maxima.
  
-%%<mjax>\mathrm{tr}(A) = \sum_{i=1}^{n}A_{ii}</mjax>%%   +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.
-<abbr title="stopa odpovídá součtu vlastních čísel a je invariantní vůči podobnosti">❓</abbr>+
  
-=== Výpočet PCA (kuchařka) s příkladem === +==== Hledání extrémů ====
-1. Spočtěte matici kovariancí   +
-%%<mjax>S = A\,A^{T}</mjax>%% +
-   +
-2. Najděte spektrální rozklad   +
-%%<mjax>S = V\,\Lambda\,V^{T},\quad \lambda_{1}\ge\cdots\ge\lambda_{m}</mjax>%%  +
  
-3. Rozdělte ortonormální bázi \(V = [\,X\mid Y\,]\)  +Najít extrém neznamená jen najít hodnotu funkce, ale určit i bod, kde se nachází, a typ extrému.
-  +
-4. Projekce dat na \(k\)-rozměrný podprostor:   +
-%%<mjax>\widehat A = X\,X^{T}A</mjax>%%  +
-  +
-5. Chyba proložení:   +
-%%<mjax>\|A-\widehat A\|_{F}^{2} = \sum_{i=k+1}^{m}\lambda_{i}</mjax>%%  +
  
-**Příklad pro**   +  * **Volné extrémy**: použijeme **podmínku nulového gradientu** a **Hessovu matici** pro test typu extrému. 
-%%<mjax>A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\;k=1.</mjax>%%   +  * **Vázané extrémy**: použijeme **Lagrangeovy multiplikátory**.
-- %%<mjax>S = AA^{T} = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}</mjax>%%   +
-- 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:+==== Příklady ====
  
-=== Singulární rozklad matice (SVD) ===+1. **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í.
  
-**Definice:** Pro libovolnou matici \(A\in\mathbb{R}^{m\times n}\) existují ortogonální matice   +2. **Vázaný extrém:** 
-\(U\in\mathbb{R}^{m\times m}\), \(V\in\mathbb{R}^{n\times n}\) a diagonální matice   +  * Minimalizujeme %%<mjax>f(x, y) = x^2 + y^2</mjax>%%   
-\(\Sigma\in\mathbb{R}^{m\times n}\) se singulárními čísly   +  * za podmínky %%<mjax>x + y = 1</mjax>%%   
-\(s_{1}\ge s_{2}\ge\cdots\ge s_{p}\ge0\) \((p=\min\{m,n\})\),   +  * Extrém se hledá pouze na přímce, ne na celé rovině.
-ž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:**+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í.
  
-1. Spočtěte matice   +==== Dělení extrémů podle kontextu ====
-%%<mjax>AA^{T}=U\,S\,U^{T},\quad A^{T}A=V\,S\,V^{T}</mjax>%%   +
-<abbr title="S je diagonální matice s_i^2, vlastní čísla AAᵀ a AᵀA">❓</abbr>+
  
-2. Sloupce U jsou vlastní vektory matice \(AA^{T}\), sloupce V vlastní vektory \(A^{T}A\).  +| Typ extrému   | Omezení            | Podmínky hledání       | 
-  +|---------------|--------------------|-------------------------| 
-3. Singulární čísla \(s_{i}=\sqrt{S_{ii}}\). +| Volný         | žádné              | derivace = 0            | 
-  +| Vázaný        | rovnosti / nerovnosti | Lagrange, KKT podmínky  | 
-==Eckart–Youngova věta==+| Globální      | celé D             | extrém celé množiny     | 
 +| Lokální       | okolí bodu         | extrém v nějaké kouli   |
  
-Nechť \(A\in\mathbb{R}^{m\times n}\), \(p=\min\{m,n\}\) a \(k\le p\). Řešením úlohy   +===== 5. Volné lokální extrémy diferencovatelných funkcí =====
-%%<mjax>\min_{\mathrm{rank}(B)\le k}\|A - B\|_{F}^{2}</mjax>%%   +
-je matice   +
-%%<mjax> +
-B^{*} +
-= U\,S_{k}\,V^{T} +
-= \sum_{i=1}^{k} s_{i}\,u_{i}\,v_{i}^{T} +
-</mjax>%%  +
  
-kde   +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.
-%%<mjax> +
-S_{k} +
-= \mathrm{diag}(s_{1},\dots,s_{k},0,\dots,0)\in\mathbb{R}^{p\times p} +
-</mjax>%%  +
  
-**Aplikace SVD:**   +=== Podmínka 1. řádu ===
-  * 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ě ℝⁿ =====+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>
  
-Nechť \(f: D \subseteq \mathbb{R}^{n} \to \mathbb{R}\), kde \(D\) je podmnožina ℝⁿ.+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“.
  
-=== Definice globálních a lokálních extrémů === +=== Podmínka 2. řádu ===
-  * **Globální minimum**:+
  
-bod \(x^{*}\in D\) je globální minimum, pokud   +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í. 
-%%<mjax>f(x^{*}) \le f(x)\quad \forall\,x\in D.</mjax>%%   +  * Pokud je \( H \succ 0 \), jedná se o ostré lokální minimum.   
-  * **Globální maximum**:+  * 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.
  
-bod \(x^{*}\in D\) je globální maximum, pokud   
-%%<mjax>f(x^{*}) \ge f(x)\quad \forall\,x\in D.</mjax>%%   
-  * **Lokální minimum**: 
  
-bod \(x^{*}\in D\) je lokální minimum, pokud existuje otevřené okolí \(U \subset D\) takové, že   +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.
-%%<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   +==== Numerické metody ====
-%%<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.+Když analyticky nelze najít řešení, použijeme **iterační metody** – postupně se přibližujeme k optimu:
  
-Pro nalezení lok min a max použijeme Hessovu matici a nulové první derivace. +  * **Obecná iterace:**   
-  +    * Volíme počáteční bod \(x_0\), směr \(v_k\) a krok \(\alpha_k > 0\)   
-===== Vázané extrémy pomocí Lagrangeových multiplikátorů =====+    * 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>%%  
  
-Pokud pro funkci \(f(x)\) hledáme extrém pod podmínkami   +  * V každém kroku tedy jdeme směrem, který zaručeně zmenšuje hodnotu funkce – tím se přibližujeme k minimu.
-\[ +
-g_{i}(x)=0,\quad i=1,\dots,m, +
-\]   +
-postupujeme následovně:+
  
-**Lagrangeova funkce:**  +  * **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>%%   
-  Definujeme   +    * Jednoduchá, ale může **konvergovat pomalu** nebo klesat příliš „cikcak“ → závisí na volbě kroku.  
-%%<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:**  +  * Jde o nejjednodušší metodu: jdeme „dolů z kopce“ po nejstrmější cestě, ale bez přizpůsobení křivosti terénu.
  
-Hledáme \((x^{*},\lambda^{*})\) tak, aby   +  * **Newtonova metoda:**   
-%%<mjax>\nabla_{x}\mathcal{L}(x^{*},\lambda^{*}) = 0, g_{i}(x^{*}) = 0,\;i=1,\dots,m</mjax>%%   +    * Zohledňuje zakřivení funkce pomocí Hessovy matice:  %%<mjax>x_{k+1} = x_k - H_f(x_k)^{-1} \nabla f(x_k)</mjax>%%   
-<abbr title="∇ₓL=0 zajišťuje stacionaritu na povrchu definovaném rovnostmi g_i=0">❓</abbr>  +    * Rychlá (kvadratická) konvergence, ale výpočetně náročná – vyžaduje inverzi Hessovy matice.  
  
-**Kontrola hranic domény (pokud je doména omezená nebo existují jiné ohraničení):**  +  * Funguje dobře, pokud máme „dobrý start“ a funkce je pěkně zakřivená – jinak může selhat.
-  +
-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:** +  * **Gauss-Newtonova metoda:**   
-   +    * Vhodná pro funkce, které jsou kvadrátem vektorové funkce \( f(x) = \|g(x)\|_2^2 \)   
-Označme Hessian Lagrangeovy funkce vzhledem k \(x\) jako   +    * Iterace:  %%<mjax>x_{k+1} = x_k - \left(J^T J\right)^{-1} J^T g(x_k)</mjax>%%   
-%%<mjax>H(x,\lambda) = \nabla^{2}_{xx}\mathcal{L}(x,\lambda).</mjax>%%   +    * kde \( J \) je Jacobiho matice funkce \( g(x) \)  
-  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:**  +  * Gauss-Newton je zjednodušená verze Newtonovy metody, která používá jen první derivace. 
-  + 
-  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ě.   +  * **Levenberg-Marquardtova metoda:**   
-   +    * Kombinuje robustnost gradientní metody s rychlostí Gauss-Newtonovy   
-===== Úloha lineárního programování (LP) =====+    * 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=== === Úvod k teorii lineárního programování, geometrický význam===
  
 Lineární programování (LP) pracuje s lineární cílovou funkcí 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**     * **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)**   +  * **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**   +  * **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)**     * **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**     * **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 ===   === Základní tvar LP ===  
 +
 Obecná formulace (kanonický tvar v „nerovnicích“) je: Obecná formulace (kanonický tvar v „nerovnicích“) je:
  
Line 595: Line 624:
 Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav: Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav:
  
-1. **Přidání nezáporných slack proměnných**   +1. **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>%%  + 
 +2. **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>%%
  
-2. **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):**   **Původní úloha (max):**  
Line 629: Line 675:
 \] \]
  
-=== Typické použití LP ===   +=== 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. 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∞ === === Kompletní příklad přeurčené soustavy v L₁ a L∞ ===
Line 764: Line 817:
 === Řešení lineárního programu (stručně) === === Ř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**     * **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)**     * **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: • b0b36dbs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b0b33opt (generated for current page)