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 18:01] – 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 718: Line 718:
 == L₁-norm (taxicab-norma) == == L₁-norm (taxicab-norma) ==
   * 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>%%   * 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>%%
-  * 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},\quadu_{i}\;\ge\; 0,\;i=1,\dots,m.</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.   * Nalezené \(\{u_{i}^{*}\}\) jsou pak absolutní odchylky a \(\sum_i u_i^*\) je minimální součet.
  
Line 835: Line 835:
     * **Nevýhoda:** V krajních případech může cyklit (řeší se např. Blandovým pravidlem).     * **Nevýhoda:** V krajních případech může cyklit (řeší se např. Blandovým pravidlem).
  
-===== Dualita v LP =====+===== 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í. 
  
  

Trace: • prednasky

Navigation

Playground

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