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

Navigation

Playground

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