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 18:09] – [Dualita v LP] 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 873: Line 873:
     * 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>     * 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:

Navigation

Playground

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