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:16] – [Podmínky konvexity podle derivací] 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 912: Line 912:
   * **Komplementární podmínky:**   * **Komplementární podmínky:**
     * Jsou splněny právě tehdy, když jsou obě řešení optimální:     * Jsou splněny právě tehdy, když jsou obě řešení optimální:
-      * Pro každé \(i\):   +      * Pro každé \(i\): %%<mjax>x_i > 0 \;\Rightarrow\; (A^T y)_i = c_i</mjax>%% 
-        %%<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>%%   
-      * Pro každé \(j\):   +      * 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>
-        %%<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**.   * Jinými slovy: **každá podmínka buď svazuje řešení (aktivní), nebo má nulový stínový dopad**.
Line 956: Line 953:
 Pokud je \(f\) dvakrát diferencovatelná: Pokud je \(f\) dvakrát diferencovatelná:
  
-  * **2. derivace – Hessova podmínka:** Funkce \(f\) je konvexní ⇔ její Hessova matice je 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>+  * **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 ==== ==== Úloha konvexní optimalizace ====

Trace:

Navigation

Playground

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