The wiki page is under active construction, expect bugs.

Differences

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

--- statnice:bakalar:b0b33opt [2025/06/04 15:53] – 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 447: / Line 447: @@
 ===== 5. Volné lokální extrémy diferencovatelných funkcí =====
-Zde hledáme minimum nebo maximum funkce \( f:\mathbb{R}^n \to \mathbb{R} \) **bez jakýchkoli omezení**.
+Zde hledáme extrémy hladkých funkcí \( f:\mathbb{R}^n \to \mathbb{R} \) **bez omezení** – tedy volné extrémy uvnitř definičního oboru.
-==== Podmínka 1. řádu ====
+=== Podmínka 1. řádu ===
 Stacionární bod \( x^* \) je kandidát na extrém, pokud platí:
@@ Line 455: / Line 455: @@
 <abbr title="Gradient v bodě x^* musí zmizet – žádný směr, kterým se hodnota f mění.">❓</abbr>
-==== Podmínka 2. řádu ====
+To znamená, že funkce nemá v tomto bodě žádný směr, kterým by mohla růst nebo klesat – ležíme v „rovnovážné poloze“.
-Pro rozhodnutí, zda jde o minimum, maximum nebo sedlový bod, použijeme **Hessovu matici** \( H_f(x) \) – matici druhých derivací.
+=== Podmínka 2. řádu ===
-V bodě \( x^* \) platí:
+Pro rozhodnutí typu stacionárního bodu, zda jde o minimum, maximum nebo sedlový bod, použijeme **Hessovu matici** \( H_f(x) \) – matici druhých derivací.
+  * Pokud je \( H \succ 0 \), jedná se o ostré lokální minimum.
+  * Pokud je \( H \succeq 0 \), jde o minimum, které ale nemusí být ostré.
+  * Pokud je \( H \prec 0 \), máme ostré lokální maximum.
+  * Pokud je \( H \preceq 0 \), jde o maximum, které nemusí být ostré.
+  * Pokud je Hessova matice indefinitní, jedná se o sedlový bod – tedy žádný extrém.
-| Vlastnosti Hessovy matice  | Typ extrému                |
-|----------------------------|----------------------------|
+Tato klasifikace vychází z tvaru funkce v okolí bodu – pomocí křivosti poznáme, zda se funkce chová jako dno mísy, vrchol kopce nebo sedlo.
-| \( H \succ 0 \)            | ostré minimum              |
-| \( H \prec 0 \)            | ostré maximum              |
-| indefinitní               | sedlový bod (žádný extrém) |
-| semidefinitní             | nelze rozhodnout (potřeba vyšší řád) |
 ==== Numerické metody ====
@@ Line 472: / Line 473: @@
 Když analyticky nelze najít řešení, použijeme **iterační metody** – postupně se přibližujeme k optimu:
-  * **Gradientní metoda** – jdeme ve směru největšího poklesu:
+  * **Obecná iterace:**
-    %%<mjax>x_{k+1} = x_k - \alpha_k \nabla f(x_k)</mjax>%%
+    * Volíme počáteční bod \(x_0\), směr \(v_k\) a krok \(\alpha_k > 0\)
-    <abbr title="αₖ je krok – jak daleko jdeme po gradientu">❓</abbr>
+    * Iterace:  %%<mjax>x_{k+1} = x_k + \alpha_k v_k</mjax>%%
+    * Směr \(v_k\) je **sestupný**, pokud:  %%<mjax>\nabla f(x_k)^T v_k < 0</mjax>%%
-  * **Newtonova metoda** – zohledňuje zakřivení funkce pomocí Hessovy matice:
+  * V každém kroku tedy jdeme směrem, který zaručeně zmenšuje hodnotu funkce – tím se přibližujeme k minimu.
-    %%<mjax>x_{k+1} = x_k - H_f(x_k)^{-1} \nabla f(x_k)</mjax>%%
-    <abbr title="rychlá konvergence, ale náročná výpočetně kvůli inverzi H">❓</abbr>
-  * **Gauss-Newtonova metoda** – zjednodušení pro kvadratické funkce:
+  * **Gradientní metoda (největší spád):**
-    používá přibližný tvar Hessovy matice bez druhých derivací.
+    * Směr je záporný gradient:  %%<mjax>x_{k+1} = x_k - \alpha_k \nabla f(x_k)</mjax>%%
+    * Jednoduchá, ale může **konvergovat pomalu** nebo klesat příliš „cikcak“ → závisí na volbě kroku.
-  * **Levenberg-Marquardtova metoda** – kombinuje vlastnosti gradientní a Gauss-Newtonovy metody pro robustní chování.
+  * Jde o nejjednodušší metodu: jdeme „dolů z kopce“ po nejstrmější cestě, ale bez přizpůsobení křivosti terénu.
+  * **Newtonova metoda:**
+    * Zohledňuje zakřivení funkce pomocí Hessovy matice:  %%<mjax>x_{k+1} = x_k - H_f(x_k)^{-1} \nabla f(x_k)</mjax>%%
+    * Rychlá (kvadratická) konvergence, ale výpočetně náročná – vyžaduje inverzi Hessovy matice.
+  * Funguje dobře, pokud máme „dobrý start“ a funkce je pěkně zakřivená – jinak může selhat.
+  * **Gauss-Newtonova metoda:**
+    * Vhodná pro funkce, které jsou kvadrátem vektorové funkce \( f(x) = \|g(x)\|_2^2 \)
+    * Iterace:  %%<mjax>x_{k+1} = x_k - \left(J^T J\right)^{-1} J^T g(x_k)</mjax>%%
+    * kde \( J \) je Jacobiho matice funkce \( g(x) \)
-===== Vázané extrémy pomocí Lagrangeových multiplikátorů =====
+  * Gauss-Newton je zjednodušená verze Newtonovy metody, která používá jen první derivace.
-Pokud pro funkci \(f(x)\) hledáme extrém pod podmínkami
+  * **Levenberg-Marquardtova metoda:**
-\[
+    * Kombinuje robustnost gradientní metody s rychlostí Gauss-Newtonovy
-g_{i}(x)=0,\quad i=1,\dots,m,
+    * Iterace:  %%<mjax>x_{k+1} = x_k - \left(J^T J + \mu I\right)^{-1} J^T g(x_k)</mjax>%%
-\]
+    * Parametr \( \mu > 0 \) umožňuje plynule přecházet mezi oběma metodami
-postupujeme následovně:
-**Lagrangeova funkce:**
+  * Pokud Gauss-Newton selhává, přidáme regularizační člen \( \mu I \), čímž omezíme „skoky“ v citlivých oblastech – metoda se chová stabilněji.
-  Definujeme
-%%<mjax>\mathcal{L}(x,\lambda) = f(x) - \sum_{i=1}^{m} \lambda_{i}\,g_{i}(x)</mjax>%%
-  kde \(\lambda = (\lambda_{1},\dots,\lambda_{m})\) jsou Lagrangeovy multiplikátory.
-**Nutné podmínky (stacionární body) na hladké části povrchu:**
-Hledáme \((x^{*},\lambda^{*})\) tak, aby
-%%<mjax>\nabla_{x}\mathcal{L}(x^{*},\lambda^{*}) = 0, g_{i}(x^{*}) = 0,\;i=1,\dots,m</mjax>%%
-<abbr title="∇ₓL=0 zajišťuje stacionaritu na povrchu definovaném rovnostmi g_i=0">❓</abbr>
-**Kontrola hranic domény (pokud je doména omezená nebo existují jiné ohraničení):**
+===== 6. Lokální extrémy diferencovatelných funkcí vázané rovnostmi =====
-Kromě vnitřních stacionárních bodů na povrchu \(\{g_i(x)=0\}\) je třeba zkontrolovat i body, kde povrch naráží na hranici původní množiny \(D\) (např. krajní body, rohy). V těchto bodech se gradient \(\nabla_{x}\mathcal{L}\) nemusí rovnat nule, ale mohou vzniknout extrémy právě kvůli hranici. Zároveň musíme vyšetřit i původní funkci \(f(x)\) pro extrémy, které spadnou do omezení.
-**Druhé řádové podmínky (určení typu extrému) na povrchu:**
+Pokud hledáme extrém funkce \( f(x) \) za podmínky, že proměnné \( x \in \mathbb{R}^n \) musí splňovat rovnosti \( g_i(x) = 0 \), musíme vzít v úvahu nejen chování samotné funkce, ale i **omezení**, která určují přípustné body.
-Označme Hessian Lagrangeovy funkce vzhledem k \(x\) jako
-%%<mjax>H(x,\lambda) = \nabla^{2}_{xx}\mathcal{L}(x,\lambda).</mjax>%%
-  Pro každý kandidátní bod \(x^{*}\) (splňující \(g_i(x^{*})=0\) a případně ležící na hranici domény) zkontrolujeme definitnost zrestrikovaného Hessianu \(H(x^{*},\lambda^{*})\) na podprostoru tangentu k množině \(\{g_{i}(x)=0\}\):
-  * Pokud je zrestrikovaný Hessian pozitivně definitní, pak \(x^{*}\) je lokální minimum.
-  * Pokud je zrestrikovaný Hessian negativně definitní, pak \(x^{*}\) je lokální maximum.
-  * Jinak je \(x^{*}\) sedlovým bodem na povrchu definovaném omezeními.
-<abbr title="kontrola Hessianu na podprostoru tangentu zajišťuje, že extrém leží na povrchu omezení">❓</abbr>
-**Výběr globálního extrému na omezeném prostoru:**
+Taková úloha má tvar:
+%%<mjax>\min f(x)\quad \text{za podmínky}\quad g_1(x) = 0,\,\dots,\,g_m(x) = 0</mjax>%%
-  Z nalezených stacionárních bodů \(x^{*}\) (na povrchu a případně na hranici domény) vybereme ty, které splňují druhé řádové podmínky pro požadovaný typ (minimum nebo maximum) a porovnáme jejich hodnoty \(f(x^{*})\). Nejmenší (nebo největší) hodnota mezi nimi je globálním extrémem na omezeném množině.
-===== Ú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).
+Tyto rovnosti určují množinu povolených řešení – tzv. **povrch**. Extrém hledáme **na tomto povrchu**, tedy jen mezi body, které splňují dané podmínky.
+=== Podmínka prvního řádu – Lagrangeovy multiplikátory ===
+Podmínky řešíme pomocí **Lagrangeovy funkce**:
+%%<mjax>\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)</mjax>%%
+<abbr title="Spojuje funkci a omezení do jediné funkce, jejíž stacionární body dávají kandidáty na extrém.">❓</abbr>
+Bod \( x^* \in \mathbb{R}^n \) je kandidátem na extrém, pokud existuje vektor multiplikátorů \( \lambda = (\lambda_1,\dots,\lambda_m) \), takový že:
+  * %%<mjax>\nabla_x \mathcal{L}(x^*, \lambda) = \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) = 0</mjax>%%
+  * %%<mjax>g_i(x^*) = 0\quad \text{pro všechna } i = 1,\dots,m</mjax>%%
+Tato podmínka říká, že v bodě \( x^* \) je gradient funkce \( f \) lineární kombinací gradientů omezení \( g_i \) – tedy **ležící v ortogonálním doplňku tečného prostoru**.
+Jinými slovy: v optimu se nelze „vydat směrem“ uvnitř množiny bez toho, aby se zvyšovala hodnota funkce.
+=== Geometrická interpretace ===
+Tečný prostor k množině \( \{x \mid g(x) = 0\} \) v bodě \( x^* \) je tvořen vektory \( v \), pro které platí: %%<mjax>g'(x^*) v = 0</mjax>%%
+– tedy množinou vektorů kolmých na gradienty omezení.
+Gradient funkce \( f \) musí ležet ve směru normály, tj. být kombinací \(\nabla g_i\).
+=== Druhý řád – určení typu extrému ===
+Hessovu matici Lagrangeovy funkce vzhledem k \( x \) označme:
+%%<mjax>H(x, \lambda) = \nabla^2_{xx} \mathcal{L}(x, \lambda)</mjax>%%
+Pro rozhodnutí o typu extrému:
+  * Zkoumáme **zrestrikovaný Hessian** na tečný prostor množiny \( \{g_i(x)=0\} \),
+  * Pokud je pozitivně definitní, jde o **lokální minimum**,
+  * Pokud negativně definitní, jde o **lokální maximum**,
+  * Pokud není ani jedno – **sedlový bod**.
+=== Kontrola hranic množiny ===
+Pokud množina \( D \), na které optimalizujeme, má i ohraničení, musíme kromě stacionárních bodů vyšetřit i **hranici domény** – extrém může vzniknout právě tam, i když nevyhoví podmínce \( \nabla_x \mathcal{L} = 0 \).
+To zahrnuje:
+  * krajní body množiny,
+  * místa, kde se gradienty omezení stávají lineárně závislými,
+  * a další situace, kdy už neplatí standardní podmínky.
+=== Postup ===
+  - Sestavíme Lagrangeovu funkci \( \mathcal{L}(x,\lambda) = f(x) + \lambda^T g(x) \).
+  - Najdeme kandidátní body \( (x^*, \lambda^*) \), které splňují:
+    * \( \nabla_x \mathcal{L}(x^*, \lambda^*) = 0 \)
+    * \( g_i(x^*) = 0 \)
+  - Zkontrolujeme druhý řád – restrikci Hessovy matice.
+  - Pokud je doména omezená, zkontrolujeme i hraniční body.
+  - Vybereme bod s nejlepší hodnotou \( f(x^*) \).
+=== Aplikace ===
+Lagrangeovy multiplikátory umožňují řešit mnoho praktických úloh:
+  * minimalizace nákladů při daných zdrojích,
+  * optimalizace návrhů pod strukturálními podmínkami,
+  * nalezení extrému na parametrické křivce nebo ploše,
+  * ekonomické rovnováhy s rozpočtovým omezením.
+===== 7. Úloha lineárního programování (LP) =====
+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 570: / 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**
+. **Vyjádření neomezených reálných proměnných** (převedení volných proměnných)
-   Každou proměnnou \(x_{j}\), která nemá nenegativní omezení, zapíšeme jako rozdíl dvou nezáporný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>%%
-%%<mjax>x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+} \ge 0,\; x_{j}^{-} \ge 0.</mjax>%%
+==== Varianty zadání ====
-=== Převod LP do kanonického tvaru (struč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>%%
+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.
+==== Převod LP do kanonického tvaru ====
 **Původní úloha (max):**
@@ Line 604: / 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 739: / 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: • b0b36dbs

Differences

Search

Navigation

Print/export

Tools

QR Code