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: • b0b33opt • b4b01num • b4b33alg • b4b36sin • be4m33ssu • prednasky

Navigation

Playground

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