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 17:57] – [Úloha lineárního programování (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 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).
  
 +===== 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:

Navigation

Playground

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