Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b0b33opt [2025/06/04 16:47] – [Vázané extrémy pomocí Lagrangeových multiplikátorů] zapleka3
+++ statnice:bakalar:b0b33opt [2025/06/12 10:33] (current) – [Podmínky konvexity podle derivací] el_dusto
@@ Line 1: / Line 1: @@
-==== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita. ====
+====== Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programová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]]
@@ Line 577: / Line 577: @@
   * ekonomické rovnováhy s rozpočtovým omezením.
-===== Úloha lineárního programování (LP) =====
+===== 7. Úloha lineárního programování (LP) =====
-Lineární programování (LP) je optimalizační disciplína, ve které hledáme vektor \(x\in\mathbb{R}^n\), který minimalizuje (nebo maximalizuje) lineární cílovou funkci za předpokladu, že \(x\) splňuje soustavu lineárních omezení (nerovnic nebo rovnic).
+Lineární programování (LP) je metoda pro **optimalizaci lineární funkce** při **lineárních omezeních**. Typicky hledáme maximum nebo minimum nějakého cíle (např. zisku, výkonu) za omezených podmínek (rozpočet, kapacita, suroviny apod.)
 === Úvod k teorii lineárního programování, geometrický význam===
 Lineární programování (LP) pracuje s lineární cílovou funkcí
-%%<mjax>z = c^{T}x</mjax>%%
+%%<mjax>z = c^{T}x</mjax>%% <abbr title="Minimalizujeme lineární funkci cᵀx při lineárních omezeních na x.">❓</abbr>
-a konvexním polyedrem definovaným lineárními omezeními (rovnicemi či nerovnicemi). Hlavními body teorie jsou:
+a konvexním polyedrem definovaným lineárními omezeními (rovnicemi či nerovnicemi).
+Hlavními body teorie jsou:
   * **Konvexní polyedr a vrcholy**
-  Soubor všech \(x\) splňujících
+    * soubor všech \(x\) splňujících %%<mjax>A\,x \ge b,\;x \ge 0</mjax>%%
-%%<mjax>A\,x \ge b,\;x \ge 0</mjax>%%
+    * tvoří konvexní množinu (polyedr). Každý takový polyedr lze popsat buď jako průnik poloprostorů, nebo jako konvexní obal (konvexní kombinace) svých extrémních bodů (vrcholů) a hran (hranové body).
-  tvoří konvexní množinu (polyedr). Každý takový polyedr lze popsat buď jako průnik poloprostorů, nebo jako konvexní obal (konvexní kombinace) svých extrémních bodů (vrcholů) a hran (hranové body).
+    * = Řešení soustavy omezení \( A x \le b \) tvoří konvexní oblast v prostoru.
   * **Vrcholy (extermální body)**
-  Vrcholem (extrémním bodem) polyedru rozumíme bod, který nelze vyjádřit jako konvexní kombinaci dvou jiných bodů v polyedru. Algebraicky to odpovídá základnímu (basic) řešení:
+    * vrcholem (extrémním bodem) polyedru rozumíme bod, který nelze vyjádřit jako konvexní kombinaci dvou jiných bodů v polyedru. Algebraicky to odpovídá základnímu (basic) řešení:
-  - Pokud máme \(m\) lineárních rovnic (po úpravě do standardního tvaru) a \(n\) proměnných, každý vrchol odpovídá výběru \(m\) nezávislých (bázových) proměnných, ostatní se nastaví na nulu.
+      * Pokud máme \(m\) lineárních rovnic (po úpravě do standardního tvaru) a \(n\) proměnných, každý vrchol odpovídá výběru \(m\) nezávislých (bázových) proměnných, ostatní se nastaví na nulu.
+    * = Body, které nelze napsat jako průměr jiných bodů v oblasti – právě v těchto bodech může ležet optimum.
   * **Optimum leží ve vrcholu**
-  Vzhledem k tomu, že
+    * vzhledem k tomu, že %%<mjax>z = c^{T}x</mjax>%%
-%%<mjax>z = c^{T}x</mjax>%%
+    * je lineární, musí globální optimum (minimální či maximální hodnota) na konvexním polyedru nastat alespoň v jednom vrcholu. Jinými slovy, pro LP není třeba zkoumat vnitřek polyedru: stačí prohledat vrcholy (popř. hrany mezi dvěma vrcholy, pokud existuje více optimálních vrcholů).
-je lineární, musí globální optimum (minimální či maximální hodnota) na konvexním polyedru nastat alespoň v jednom vrcholu. Jinými slovy, pro LP není třeba zkoumat vnitřek polyedru: stačí prohledat vrcholy (popř. hrany mezi dvěma vrcholy, pokud existuje více optimálních vrcholů).
+    * = Pokud má LP optimum, pak existuje alespoň v jednom z vrcholů této oblasti. Nemusíme tedy prohledávat celý prostor, stačí kontrolovat vrcholy.
   * **Více optimálních vrcholů (degenerace)**
-Pokud existují dva vrcholy \(x^{(1)}, x^{(2)}\) s
+    * Pokud existují dva vrcholy \(x^{(1)}, x^{(2)}\) s %%<mjax>c^{T}x^{(1)} = c^{T}x^{(2)} = z^{*},</mjax>%%
-%%<mjax>c^{T}x^{(1)} = c^{T}x^{(2)} = z^{*},</mjax>%%
+    * pak každá konvexní kombinace %%<mjax>x = \alpha\,x^{(1)} + (1-\alpha)\,x^{(2)},\quad 0\le\alpha\le1,</mjax>%%
-pak každá konvexní kombinace
+    * je také optimální a leží na hraně spojující tyto dva vrcholy. To znamená, že optimální množina může být celá hrana (nejen izolovaný vrchol).
-%%<mjax>x = \alpha\,x^{(1)} + (1-\alpha)\,x^{(2)},\quad 0\le\alpha\le1,</mjax>%%
+    * = Pokud má více vrcholů stejnou hodnotu cílové funkce, optimum je libovolná jejich kombinace – tedy i celé hrany mezi nimi.
-je také optimální a leží na hraně spojující tyto dva vrcholy. To znamená, že optimální množina může být celá hrana (nejen izolovaný vrchol).
   * **Geometrické důsledky**
-  - Pokud polyedr nemá žádné vrcholy (např. neomezená směrově čtvercová množina), může optimum neexistovat (např. LP cílová funkce neklesá) nebo být dosaženo jen „v nekonečnu“.
+    - Pokud polyedr nemá žádné vrcholy (např. neomezená směrově čtvercová množina), může optimum neexistovat (např. LP cílová funkce neklesá) nebo být dosaženo jen „v nekonečnu“.
-  - Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.
+    - Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.
 === Základní tvar LP ===
 Obecná formulace (kanonický tvar v „nerovnicích“) je:
@@ Line 621: / Line 624: @@
 Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav:
-. **Přidání nezáporných slack proměnných**
+. **Přidání nezáporných slack proměnných** (nerovností na rovnosti)
-   Pro každé omezení ve tvaru nerovnosti (např. \(a_{i}^{T}x \le b_{i}\)) přidáme novou proměnnou \(u_{i} \ge 0\), aby vznikla rovnice
+  * Pro každé omezení ve tvaru nerovnosti (např. \(a_{i}^{T}x \le b_{i}\)) přidáme novou proměnnou \(u_{i} \ge 0\), aby vznikla rovnice %%<mjax>a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.</mjax>%%
-%%<mjax>a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.</mjax>%%
+. **Vyjádření neomezených reálných proměnných** (převedení volných proměnných)
+  * Každou proměnnou bez znaménkového omezení rozložíme jako rozdíl dvou nezáporných: %%<mjax>x_j = x_j^+ - x_j^-,\quad x_j^+,\,x_j^- \ge 0</mjax>%%
+==== Varianty zadání ====
+Úlohu LP lze převádět mezi různými tvary – např. aby vyhovovala algoritmům (simplex, metoda vnitřního bodu) nebo vizualizaci.
+  * **Minimalizace vs. maximalizace:**
+    * Maximalizaci převedeme na minimalizaci změnou znaménka: %%<mjax>\max c^T x \equiv \min (-c)^T x</mjax>%%
+  * **Rovnosti a nerovnosti:**
+    * Rovnost převedeme na dvě opačné nerovnosti: %%<mjax>a^T x = b \equiv a^T x \le b \ \text{a} \ -a^T x \le -b</mjax>%%
+  * **Proměnné bez znaménka:**
+    * Volná proměnná se nahradí rozdílem dvou nezáporných: %%<mjax>x_i = x_i^+ - x_i^-,\quad x_i^+, x_i^- \ge 0</mjax>%%
+  * **Slack proměnné (u nerovností):**
+    * Každou nerovnost \(a_i^T x \le b_i\) převedeme na rovnici přidáním nové nezáporné proměnné: %%<mjax>a_i^T x + s_i = b_i,\quad s_i \ge 0</mjax>%%
-. **Vyjádření neomezených reálných proměnných**
+Tím dostaneme **kanonický tvar LP** – s rovnicemi a nezápornými proměnnými, se kterým umí pracovat všechny běžné algoritmy.
-   Každou proměnnou \(x_{j}\), která nemá nenegativní omezení, zapíšeme jako rozdíl dvou nezáporných proměnných:
-%%<mjax>x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+} \ge 0,\; x_{j}^{-} \ge 0.</mjax>%%
-=== Převod LP do kanonického tvaru (stručně) ===
+==== Převod LP do kanonického tvaru ====
 **Původní úloha (max):**
@@ Line 655: / Line 675: @@
 \]
 === Typické použití LP ===
-LP se uplatňuje v mnoha oblastech, například:
-  * **Plánování výroby a alokace zdrojů** – maximalizace zisku z produktů nebo minimalizace výrobních nákladů, kde \(x_j\) jsou počty vyrobených jednotek, \(A\,x \le b\) zachycuje omezení surovin, kapacit, pracovních hodin.
-  * **Směrování a toky v síti** – minimalizace nákladů na přepravu z bodu A do B s omezeními kapacit hran; LP formulace pro \emph{min-cost flow}.
-  * **Optimalizace transportních problémů (assignment, transporte, dietă)** – přiřazení zaměstnanců úkolům, sklady-prodejny-dodávky, minimální náklady na dietní plán.
-=== Přibližné řešení přeurčených soustav ===
+Lineární programování se používá v různých oborech, kde je třeba nalézt nejlepší možné řešení za daných podmínek:
-Uvažujme přeurčenou soustavu lineárních rovnic \(A\,x \approx b\), kde \(A\in\mathbb{R}^{m\times n}\), \(m>n\). Místo klasického minimaxu v L₂-normě (least squares) můžeme hledat řešení, které minimalizuje odchylku v jiných normách – L₁ resp. L∞. Obě formulace lze přepsat jako LP.
-=== L∞-norm (max-norm) ===
+  * **Plánování výroby a alokace zdrojů**
-Chceme minimalizovat největší odchylku:
+    * Např. maximalizace zisku z produktů nebo minimalizace nákladů.
-%%<mjax>
+    * Omezující podmínky mohou být kapacity strojů, pracovní doba, množství surovin apod.
-\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{\infty}
+  * **Směrování a toky v síti**
-\;=\;\min_{x}\; \max_{i=1\dots m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|.
+    * Minimalizace nákladů na přepravu v dopravní síti.
-</mjax>%%
+    * Omezení tvoří kapacity hran a požadavky na vstup/výstup v uzlech.
-Formulujeme ekvivalentně:
+  * **Transportní a přiřazovací problémy**
-%%<mjax>
+    * Např. optimální distribuce zboží ze skladů do prodejen.
-\min_{x,\;t}\; t
+    * Přiřazování pracovníků k úkolům nebo trasám.
-\quad\text{za podmínek}\quad
+  * **Dietní problém**
--\,t \;\le\; a_{i}^{T}x - b_{i}\;\le\; t,\quad i=1,\dots,m,\quad t\in\mathbb{R}.
+    * Hledání nejlevnější kombinace potravin splňující výživové normy.
-</mjax>%%
+    * Každá potravina má známé nutriční složení a cenu.
+  * **Ekonomické rovnováhy a plánování**
+    * Například v makroekonomii při modelování rovnováh v sektorech nebo při investičním plánování.
+LP slouží jako základ pro složitější varianty – např. celočíselné, nelineární nebo stochastické programování.
+==== Přibližné řešení přeurčené soustavy ====
+Přeurčená soustava rovnic \( A x = b \), kde počet rovnic \( m \) převyšuje počet neznámých \( n \), obvykle nemá přesné řešení. Hledáme proto takové \( x \), které dává nejlepší možné přiblížení – tj. minimalizuje odchylku \( A x - b \) podle zvolené normy.
+Typické volby:
+  * **1-norma (součet absolutních odchylek):**
+    * %%<mjax>\min \|A x - b\|_1 = \sum_{i=1}^m |a_i^T x - b_i|</mjax>%% <abbr title="Robustní vůči odlehlým hodnotám – penalizuje každou chybu stejně.">❓</abbr>
+  * **∞-norma (maximální odchylka):**
+    * %%<mjax>\min \|A x - b\|_\infty = \max_{i=1,\dots,m} |a_i^T x - b_i|</mjax>%% <abbr title="Zajišťuje, že žádná rovnice není výrazně porušena – důležité při rovnoměrných požadavcích.">❓</abbr>
+Obě tyto úlohy lze převést na lineární programování (LP) zavedením pomocných proměnných a vhodných lineárních omezení.
+== L∞-norm (max-norm) ==
+  * Chceme minimalizovat největší odchylku: %%<mjax> \min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{\infty} \;=\;\min_{x}\; \max_{i=1\dots m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|. </mjax>%%
+  * Formulujeme ekvivalentně: %%<mjax> \min_{x,\;t}\; t \quad\text{za podmínek}\quad -\,t \;\le\; a_{i}^{T}x - b_{i}\;\le\; t,\quad i=1,\dots,m,\quad t\in\mathbb{R}.</mjax>%%
 Výsledkem je LP v proměnných \((x_1,\dots,x_n,t)\). Optimální \(x^{*}\) minimalizuje největší reziduum.
-=== L₁-norm (taxicab-norma) ===
+== L₁-norm (taxicab-norma) ==
-Chceme minimalizovat součet absolutních odchylek:
+  * 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>%%
-%%<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>%%
-\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{1}
+  * Nalezené \(\{u_{i}^{*}\}\) jsou pak absolutní odchylky a \(\sum_i u_i^*\) je minimální součet.
-\;=\;\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},\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.
 === Kompletní příklad přeurčené soustavy v L₁ a L∞ ===
@@ Line 790: / Line 817: @@
 === Řešení lineárního programu (stručně) ===
-Po převedení LP do kanonického (rovnicového) tvaru
+Po převedení LP do kanonického (rovnicového) tvaru %%<mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax>%%
-%%<mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax>%%
-věnujeme pozornost následujícím možnostem:
+řešíme optimalizační úlohu nad konvexní množinou řešení (polyedrem). Existuje několik přístupů:
   * **Vyhledání vrcholů a porovnání cílové funkce**
-  - Najdeme všechny vrcholy jako soustavu lineárních rovnic pro každou dvojici omezení a prohlásíme za optimum vrchol s maximální hodnotou.
+    * Všechny vrcholy polyedru odpovídají základním řešením soustavy \(A x = b\), kde \(x \ge 0\).
-  - **výhoda:** pro malé problémy ve 2D(3D) lze řešit graficky.
+    * Pro malé problémy (2D, 3D) lze vrcholy zjistit graficky jako průsečíky omezení.
-  - **Nevýhoda:** Počet vrcholů roste exponenciálně (\(\binom{n}{m}\)), takže postup je vhodný pouze pro velmi malé rozměry.
+    * Vyhodnotíme hodnotu cílové funkce \(c^T x\) ve všech vrcholech a zvolíme nejlepší.
+    * **Výhoda:** Přehledná geometrická interpretace, vhodná pro ilustraci.
+    * **Nevýhoda:** Počet vrcholů může být exponenciální (\(\binom{n}{m}\)), což je výpočetně neúnosné pro větší úlohy.
   * **Simplexová metoda (pohyb po hranách polyedru)**
-  - Namísto úplného výčtu vrcholů se pohybujeme z vrcholu na sousední vrchol, kde se hodnota cílové funkce vždy zlepšuje.
+    * Nehledáme všechny vrcholy – postupně se přesouváme z jednoho vrcholu k sousednímu, přičemž hodnota cílové funkce se zlepšuje (klesá nebo roste).
-  - Metoda prakticky najde optimální řešení ve velmi malém počtu kroků pro většinu reálných LP.
+    * V každém kroku vybíráme bázové proměnné a aktualizujeme tzv. simplexovou tabulku.
-  - **Výhoda:** Efektivní
+    * Algoritmus konverguje k optimu v konečně mnoha krocích, pokud nenastane degenerace.
-  - **Nevýhoda:** Může se zacyklit
+    * **Výhoda:** Prakticky velmi rychlý pro většinu úloh – často jen málo kroků.
+    * **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 • b4b36sin

Differences

Search

Navigation

Print/export

Tools

QR Code