====== 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]] * **Přibližné řešení lineární soustavy** – ve smyslu nejmenších čtverců, normální rovnice. Ortogonální projekce na podprostor a její matice (ortogonální projektor), vzdálenost bodu od podprostoru. Řešení nedourčené lineární soustavy s nejmenší normou. Pseudoinverze. * **Vlastní čísla a vektory** – reálné symetrické matice, její spektrální rozklad. Kvadratické formy na Rⁿ: definitnost, diagonalizace spektrálním rozkladem, minima a maxima. Kvadratické funkce na Rⁿ: doplnění na čtverec, minima a maxima. * **Optimální proložení bodů podprostorem (PCA)** – nejbližší matice nižší hodnosti (low-rank approximation), singulární rozklad matice (SVD). * **Globální a lokální extrémy funkce na podmnožině Rⁿ** – definice, příklady, volné a vázané extrémy. * **Volné lokální extrémy diferencovatelných funkcí** – podmínky prvního a druhého řádu, numerické iterační metody (gradientní a Newtonova, Gauss-Newtonova a Levenberg-Marquardtova). * **Lokální extrémy diferencovatelných funkcí vázané rovnostmi** – podmínka prvního řádu, pojem Lagrangeovy funkce a Lagrangeových multiplikátorů. * **Úloha lineárního programování (LP)** – různé tvary úloh LP a jejich převody, typická použití LP, přibližné řešení přeurčených soustav v 1-normě a max-normě. * **Geometrie LP** – konvexní množiny a mnohostěny, extremální body konvexního mnohostěnu. * **Dualita v LP** – věta o slabé dualitě, o komplementaritě, věta o silné dualitě. * **Konvexní funkce** – definice, podmínka prvního a druhého řádu, epigraf a subkontura. Úloha konvexní optimalizace. ===== 1. Přibližné řešení lineární soustavy ===== Řešení lineární soustavy rovnic pomocí **metody nejmenších čtverců**, například při **měření s chybami** nebo pokud je soustava **pře- nebo nedourčená** (má více rovnic než neznámých nebo naopak). Pomocí projekce na podprostor a pseudoinverze hledáme řešení, které buď nejlépe odpovídá pozorovaným datům, nebo má nejmenší možnou normu. ==== Nejmenší čtverce a normální rovnice ==== Metoda nejmenších čtverců slouží k přibližnému řešení soustavy rovnic $ A x \approx b $, která nemá přesné řešení – typicky když je počet rovnic větší než počet neznámých (tzv. přeurčená soustava). Hledáme vektor $ x $, který co nejlépe „vysvětlí“ data $ b $ v rámci daného lineárního modelu. Cílem je **minimalizovat součet čtverců rozdílů** (reziduí) mezi skutečnými a modelovanými hodnotami: %%\min_{x}\|A x - b\|_2^2%% ❓ Tato úloha je speciálním případem obecného problému minimalizace funkce: %%f(x) := \|g(x)\|^2 = \sum_{i=1}^{m} g_i(x)^2%% kde $ g(x) = A x - b $ je lineární (viz obrázek). Z první podmínky optimálního bodu (nulový gradient) odvodíme tzv. **normální rovnice**: %%A^T A x = A^T b%% ❓ Pokud má $ A $ **lineárně nezávislé sloupce** (tzv. full column rank), je matice $ A^T A $ regulární (invertovatelná) a řešení je jednoznačné: %%x = (A^T A)^{-1} A^T b%% ❓ Tuto metodu lze chápat jako **projekci** vektoru $ b $ na podprostor generovaný sloupci $ A $. Pokud $ b $ neleží v tomto podprostoru, hledáme nejbližší bod z tohoto podprostoru. ==== Ortogonální projekce a ortogonální projektor ==== Řešení úlohy nejmenších čtverců odpovídá **kolmé projekci** vektoru $ b $ do podprostoru $ \mathrm{rng}(A) $. Výsledkem projekce je vektor $ Ax $, který je co nejblíž vektoru $ b $ a zároveň leží v obrazu $ A $. Projektor, který provádí tuto projekci, má tvar: %%P = A (A^T A)^{-1} A^T%% ❓ Vlastnosti projektoru: * **Symetrický**: $ P = P^T $ * **Idempotentní**: $ P^2 = P $ Pro vektor $ z $ platí, že jeho projekce do podprostoru je $ P z $. Ortogonální doplněk (kolmý zbytek) je $ (I - P) z $, tedy kolik z vektoru „přebývá mimo“ podprostor. ==== Vzdálenost bodu od podprostoru ==== Vzdálenost bodu $ b $ od podprostoru $ \mathrm{rng}(A) $ měříme jako normu vektoru chyby (reziduum): %%\mathrm{dist}(b, \mathrm{rng}(A)) = \|b - P b\|_2%% ❓ To je přesně to, co minimalizujeme v úloze nejmenších čtverců – hledáme vektor $ Ax $, který je co nejblíže $ b $, a zároveň patří do obrazu $ A $. ==== Řešení nedourčené soustavy s nejmenší normou ==== Pokud je počet neznámých větší než počet rovnic, je systém **nedourčený** a má nekonečně mnoho řešení. Hledáme tedy takové řešení, které má **nejmenší normu**: %%\min_{x} \|x\|_2 \quad \text{při podmínce} \quad A x = b%% Toto řešení lze získat pomocí tzv. **pravé pseudoinverze**: %%A^+ = A^T (A A^T)^{-1}%% ❓ %%x = A^+ b%% ❓ Tato formulace platí, pokud má matice $ A $ **plný řádkový hodnost** (řádky jsou lineárně nezávislé). ==== Pseudoinverze ==== Pro libovolnou matici $ A $ existuje jedinečně definovaná **Moore–Penroseova pseudoinverze** $ A^+ $. Ta vrací buď: * **nejbližší možný obraz** v případě přeurčené soustavy * **řešení s nejmenší normou** v případě nedourčené soustavy - pokud je řešení více * řeší úlohu nejmenších čtverců, pokud $ A x = b $ nemá přesné řešení **Zápisy:** * Levá pseudoinverze (full column rank): %%A^+ = (A^T A)^{-1} A^T%% ❓ * Pravá pseudoinverze (full row rank): %%A^+ = A^T (A A^T)^{-1}%% ❓ * Obecně: %%x = A^+ b%% ❓ ==== Příklad ==== Model: %%f(x) = \alpha + \beta x%% Naměřená data: %%(x_{i},y_{i}) = (1,2),\,(2,3),\,(3,5)%% Matice a vektor: %% A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix},\quad b = \begin{pmatrix} 2 \\ 3 \\ 5 \end{pmatrix} %% Výpočty: %% A^T A = \begin{pmatrix}3 & 6\\6 & 14\end{pmatrix},\quad (A^T A)^{-1} = \frac{1}{6}\begin{pmatrix}14 & -6\\-6 & 3\end{pmatrix},\quad A^T b = \begin{pmatrix}10\\23\end{pmatrix} %% Výsledné řešení: %% \begin{pmatrix}\alpha\\\beta\end{pmatrix} = (A^T A)^{-1} A^T b = \begin{pmatrix}1/3 \\ 3/2\end{pmatrix} %% ===== 2. Vlastní čísla, kvadratické formy a kvadratické funkce ===== Tato kapitola se zaměřuje na práci s **kvadratickými výrazy** a jejich souvislost s **optimalizací**. Pomocí **vlastních čísel a vektorů** dokážeme analyzovat chování kvadratických forem, určovat **minima a maxima** a převádět funkce do jednoduššího tvaru. Důležitým nástrojem je také **spektrální rozklad** symetrických matic, který umožňuje přímou interpretaci geometrických vlastností. ==== Vlastní čísla a vektory reálných symetrických matic ==== Vlastní čísla a vektory nám říkají, jak matice mění prostor – v některých směrech pouze škáluje, bez změny směru. **Vlastní číslo** $\lambda$ je skalár, pro nějž existuje nenulový vektor $v$, takový že: %%A\,v = \lambda\,v%% ❓ Pro výpočet vlastních čísel řešíme **charakteristickou rovnici**: %%\det(A - \lambda I)=0%% ❓ Vlastní čísla i vektory hrají klíčovou roli v optimalizaci a geometrické interpretaci matic. Pokud je $ A $ **symetrická**, má: * reálná vlastní čísla, * ortogonální bázi vlastních vektorů, * **spektrální rozklad** ve tvaru: %%A = Q \Lambda Q^T%% * kde $ Q $ je ortogonální matice a $ \Lambda $ je diagonální. **Algebraická násobnost** – počet výskytů kořene v charakteristickém polynomu. **Geometrická násobnost** – dimenze jádra $(A - \lambda I)$. V ideálním případě (symetrická matice) se algebraická a geometrická násobnost rovnají. ==== Příklad výpočtu vlastních čísel a vektorů ==== Tento příklad ukazuje, jak krok za krokem nalézt vlastní čísla a odpovídající vektory. Nechť %%A = \begin{pmatrix}2 & 1 \\ 1 & 2\end{pmatrix}%% 1. **Charakteristická rovnice:** %%\det(A - \lambda I) = \det\begin{pmatrix}2-\lambda & 1 \\ 1 & 2-\lambda\end{pmatrix} = (2-\lambda)^{2} - 1 = 0%% Řešení: %%\lambda_{1}=3,\quad \lambda_{2}=1%% 2. **Vlastní prostor pro $\lambda_{1}=3$:** Řešíme %%(A - 3I)\,v = 0 \quad\Longrightarrow\quad \begin{pmatrix}-1 & 1 \\ 1 & -1\end{pmatrix} \begin{pmatrix}v_{1}\\v_{2}\end{pmatrix} = 0%% Odtud $v_{1}=v_{2}$, tedy vlastní vektor může být %%v^{(1)} = \begin{pmatrix}1\\1\end{pmatrix}%% 3. **Vlastní prostor pro $\lambda_{2}=1$:** Řešíme %%(A - I)\,v = 0 \quad\Longrightarrow\quad \begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix} \begin{pmatrix}v_{1}\\v_{2}\end{pmatrix} = 0%% Odtud $v_{1} = -\,v_{2}$, vlastní vektor může být %%v^{(2)} = \begin{pmatrix}1\\-1\end{pmatrix}%% ==== Spektrální rozklad ==== Pro každou reálnou symetrickou matici $ A $ existuje ortogonální spektrální rozklad: %%A = V \Lambda V^T%% ❓ Spektrální rozklad přepisuje symetrickou matici $A$ jako ortogonální transformaci do diagonální podoby. Využívá se pro: * snadno analyzovat kvadratické formy (rozkládají se na vážené čtverce vlastních souřadnic), * efektivně počítat funkce matice (např. mocniny nebo exponenciálu), * numericky stabilně řešit lineární a optimalizační úlohy. **Příklad:** %%V = \tfrac{1}{\sqrt{2}}\begin{pmatrix}1 & 1\\1 & -1\end{pmatrix},\;\Lambda=\begin{pmatrix}3&0\\0&1\end{pmatrix}\;\Longrightarrow\;A=V\Lambda V^{T}=\begin{pmatrix}2&1\\1&2\end{pmatrix}%% ❓ ==== Kvadratické formy na $\mathbb{R}^n$: definitnost, diagonalizace ==== Kvadratická forma je homogenní polynom druhého stupně definovaný symetrickou maticí $A$: %%f(x) = x^{T}A\,x%% ❓ Kvadratická forma nám říká, zda funkce roste nebo klesá v různých směrech – podle toho, jak vypadá matice $A$. Podle spektra (vlastních čísel) matice $ A $ rozlišujeme: * %%A \succ 0%% – pozitivně definitní ($\lambda_{i}>0$) * %%A \succeq 0%% – pozitivně semidefinitní ($\lambda_{i}\ge0$) * %%A \preceq 0%% – negativně semidefinitní ($\lambda_{i}\le0$) * %%A \prec 0%% – negativně definitní ($\lambda_{i}<0$) * jinak indefinitní (část $\lambda_{i}>0$, část $\lambda_{i}<0$) **Diagonalizace kvadratické formy:** Pomocí spektrálního rozkladu $ A = V \Lambda V^T $ a substituce $ y = V^T x $ dostaneme: %%f(x) = y^T \Lambda y = \sum_{i=1}^n \lambda_i y_i^2%% ❓ Z toho lze přímo určit, zda má forma minimum nebo maximum, a zda je extrém ostrý. **Příklad:** %% f(x) = x^T A x = y^T \Lambda y = 3 y_1^2 + 1 y_2^2,\quad y = V^T x = \tfrac{1}{\sqrt{2}}\begin{pmatrix}x_1 + x_2 \\ x_1 - x_2\end{pmatrix} %% ❓ ==== Kvadratické funkce na $\mathbb{R}^n$: doplnění na čtverec ==== Obecná kvadratická funkce má tvar: %%g(x) = x^T A x + b^T x + c%% Tato funkce obsahuje jak kvadratický, tak lineární člen – jejím cílem je najít stacionární bod a rozhodnout, zda jde o minimum, maximum nebo sedlový bod. **Doplnění na n-tý řád (Taylorův polynom):** Pro dostatečně hladkou funkci $g:\mathbb{R}^n\to\mathbb{R}$ kolem bodu $x^*$ platí Taylorův rozvoj až do $n$-tého řádu: %% g(x) = \sum_{k=0}^{n}\frac{1}{k!}\,D^{k}g(x^*)\bigl[x-x^*\bigr]^{k} + R_{n+1}(x), %% Pro hledání extrému ji přepíšeme pomocí **doplnění na čtverec**. Využíváme Taylorův polynom 2. řádu kolem bodu $ x^* $: %% T_{2}(x) = g(x^*) + \nabla g(x^*)^T (x - x^*) + \tfrac{1}{2} (x - x^*)^T \nabla^2 g(x^*) (x - x^*) %% **Stacionární bod** je: %%x^* = -A^{-1} b%% Přepsání funkce: %% g(x) = \tfrac{1}{2}(x - x^*)^T A (x - x^*) + \text{konst.} %% **Minima a maxima (na otevřené množině $\mathbb{R}^{n}$):** * $A \succ 0$: $g$ je striktně konvexní ⇒ unikátní globální minimum v $x^{*}$ * $A \prec 0$: $g$ je striktně konkávní ⇒ unikátní globální maximum v $x^{*}$ * Jinak je $x^{*}$ sedlovým bodem (žádný globální extrém) ===== 3. Optimální proložení bodů podprostorem (PCA) ===== Tato kapitola se věnuje metodám, které hledají **nejlepší aproximaci dat** v nižším rozměru. Typickým příkladem je metoda hlavních komponent (**PCA**), která minimalizuje ztrátu informace při promítání dat do podprostoru. Klíčovým nástrojem pro tuto úlohu je **singulární rozklad matice (SVD)** – univerzální technika pro analýzu struktury a „redukování“ matic. **Motivace:** Ve strojovém učení nebo klasifikaci často pracujeme s daty ve velmi vysoké dimenzi (např. tisíce rysů). PCA umožňuje zmenšit rozměr na menší podprostor tak, aby se zachoval co největší rozptyl (informace). To vede k rychlejším výpočtům, nižšímu šumu a přehlednější vizualizaci. ==== Singulární rozklad matice (SVD) ==== Každou reálnou matici $ A \in \mathbb{R}^{m \times n} $ lze zapsat ve tvaru: %%A = U \Sigma V^T%% ❓ * $ U \in \mathbb{R}^{m \times m} $ – levé singulární vektory * $ \Sigma \in \mathbb{R}^{m \times n} $ – diagonální matice singulárních čísel * $ V \in \mathbb{R}^{n \times n} $ – pravé singulární vektory Singulární čísla $ \sigma_1 \ge \cdots \ge \sigma_r > 0 $ jsou druhé odmocniny vlastních čísel matic $ A A^T $ a $ A^T A $. SVD existuje pro každou reálnou (i obdélníkovou) matici. **Výpočet SVD:** * Spočteme spektrální rozklad $ A A^T = U S U^T $ a $ A^T A = V S V^T $ * Singulární čísla $ s_i = \sqrt{S_{ii}} $ * Pak $ A = U S^{1/2} V^T $ ==== PCA jako optimalizační úloha ==== PCA můžeme chápat dvěma způsoby: * **Minimalizace chyby projekce (minimální vzdálenost od podprostoru):** * Hledáme podprostor dimenze $k$, na který promítneme data tak, aby se minimalizoval součet čtverců vzdáleností (reziduí): * %%\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}%%❓ * **Maximalizace zachyceného rozptylu (stopa):** * Volíme $X$ tak, aby projekce dat na podprostor měla co největší rozptyl: * %%\max_{X^{T}X=I}\sum_{i=1}^{n}\|X^{T}a_{i}\|_{2}^{2}= \max_{X^{T}X=I}\|X^{T}A\|_{F}^{2}= \max_{X^{T}X=I}\mathrm{tr}\bigl(X^{T}A A^{T}X\bigr)%%❓ Tyto dva přístupy vedou ke stejnému výsledku – podprostoru generovanému prvními $k$ vlastními vektory matice $A A^T$. === Aproximace maticí nižší hodnosti === Nechť $ A \in \mathbb{R}^{m \times n} $, $ p = \min\{m,n\} $ a $ k \le p $. Hledáme matici $ B $ hodnosti nejvýše $ k $, která je co nejblíže původní matici $ A $ ve Frobeniově normě: %%\min_{\mathrm{rank}(B) \le k} \|A - B\|_F%% ❓ == Eckart–Youngova věta == Tato úloha má řešení dáno oříznutím SVD rozkladu $ A = U \Sigma V^T $ na prvních $ k $ složek: %% A_k = \sum_{i=1}^{k} s_i\,u_i\,v_i^T = U\,\Sigma_k\,V^T %% kde %% \Sigma_k = \mathrm{diag}(s_1, \dots, s_k, 0, \dots, 0) \in \mathbb{R}^{m \times n} %% obsahuje jen první $ k $ singulárních čísel a zbytek nulujeme. Používáme tedy jen první $ k $ singulárních složek z rozkladu SVD – to zaručuje nejlepší možnou aproximaci v dané dimenzi. === Funkce stopa (trace) === Stopa čtvercové matice je součet diagonálních prvků: %%\mathrm{tr}(A) = \sum_{i=1}^{n} A_{ii}%% ❓ Stopu si můžeš představit jako míru „energie“ nebo rozptylu, kterou matice zachytává v prostoru – čím větší stopa, tím více informací. ==== Výpočet PCA (krok za krokem) ==== 1. Spočítáme matici kovariancí: %%S = A A^T%% * Matice $S = A A^T$ je tzv. kovarianční matice, která říká, jak moc a v jakých směrech se data mění. 2. Provedeme spektrální rozklad: %%S = V \Lambda V^T,\quad \lambda_1 \ge \cdots \ge \lambda_m%% 3. Zvolíme první $k$ vektorů: $ V = [X \mid Y] $ 4. Projekce dat: %%\widehat{A} = X X^T A%% 5. Chyba projekce: %%\|A - \widehat{A}\|_F^2 = \sum_{i=k+1}^m \lambda_i%% ❓ === Příklad === Nechť: %%A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\quad k = 1%% 1. Kovarianční matice: %%S = A A^T = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}%% 2. Spektrální rozklad: %%\lambda_1 = 9,\quad \lambda_2 = 1,\quad v_1 = \tfrac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}%% 3. Výběr podprostoru: %%X = [v_1]%% 4. Projekce: %%\widehat{A} = X X^T A = \tfrac{1}{2} \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix} = \begin{pmatrix}1.5 & 1.5\\1.5 & 1.5\end{pmatrix}%% 5. Chyba proložení: %%\|A - \widehat{A}\|_F^2 = \lambda_2 = 1%% **Interpretace:** Projekce do 1D podprostoru zachová rozptyl $ \lambda_1 $, ztráta informace odpovídá $ \lambda_2 $. PCA tedy dává nejlepší možnou redukci na danou dimenzi. ===== 4. Globální a lokální extrémy funkce na podmnožině ℝⁿ ===== Extrémy mohou být: * **volné**, tj. hledáme optimum na celé $\mathbb{R}^n$, * nebo **vázané**, kdy je funkce omezena podmínkami. V praxi často hledáme nejlepší řešení (např. nejnižší cenu, nejkratší trasu, maximální efektivitu), ať už bez omezení, nebo podmíněně – třeba za předpokladu omezených zdrojů. ==== Definice ==== Mějme funkci $ f: D \subset \mathbb{R}^n \rightarrow \mathbb{R} $. * **Lokální minimum**: existuje okolí $ U $ bodu $ x^* $, že pro všechna $ x \in U \cap D $: %%f(x) \ge f(x^*)%% * **Lokální maximum**: %%f(x) \le f(x^*)%% * **Globální minimum** (na $D$): %%f(x) \ge f(x^*)\quad\forall x \in D%% * **Globální maximum**: %%f(x) \le f(x^*)\quad\forall x \in D%% Lokální extrém je jen „nejlepší v okolí“, zatímco globální je nejlepší **v celé množině**. ==== Kdy je extrém globální ==== Pokud je funkce **konvexní**, pak **každé lokální minimum je zároveň globální minimum**. U konkávních funkcí analogicky pro maxima. Tato vlastnost je velmi důležitá v optimalizaci – nemusíme hledat celé globální optimum, stačí najít lokální a víme, že je to ono. ==== Hledání extrémů ==== Najít extrém neznamená jen najít hodnotu funkce, ale určit i bod, kde se nachází, a typ extrému. * **Volné extrémy**: použijeme **podmínku nulového gradientu** a **Hessovu matici** pro test typu extrému. * **Vázané extrémy**: použijeme **Lagrangeovy multiplikátory**. ==== Příklady ==== 1. **Volný extrém:** * Např. funkce %%f(x, y) = x^2 + y^2%% * má globální minimum v bodě %%x^* = (0, 0),\quad f(x^*) = 0%% * Jde o tvar trychtýře – minimum je ve středu a zároveň lokální i globální. 2. **Vázaný extrém:** * Minimalizujeme %%f(x, y) = x^2 + y^2%% * za podmínky %%x + y = 1%% * Extrém se hledá pouze na přímce, ne na celé rovině. Takové úlohy se řeší metodou **Lagrangeových multiplikátorů**, která převede problém s omezením na rovnici, kterou můžeme řešit pomocí derivací. ==== Dělení extrémů podle kontextu ==== | Typ extrému | Omezení | Podmínky hledání | |---------------|--------------------|-------------------------| | Volný | žádné | derivace = 0 | | Vázaný | rovnosti / nerovnosti | Lagrange, KKT podmínky | | Globální | celé D | extrém celé množiny | | Lokální | okolí bodu | extrém v nějaké kouli | ===== 5. Volné lokální extrémy diferencovatelných funkcí ===== 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 === Stacionární bod $ x^* $ je kandidát na extrém, pokud platí: %%\nabla f(x^*) = 0%% ❓ 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“. === Podmínka 2. řádu === 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. 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. ==== Numerické metody ==== Když analyticky nelze najít řešení, použijeme **iterační metody** – postupně se přibližujeme k optimu: * **Obecná iterace:** * Volíme počáteční bod $x_0$, směr $v_k$ a krok $\alpha_k > 0$ * Iterace: %%x_{k+1} = x_k + \alpha_k v_k%% * Směr $v_k$ je **sestupný**, pokud: %%\nabla f(x_k)^T v_k < 0%% * V každém kroku tedy jdeme směrem, který zaručeně zmenšuje hodnotu funkce – tím se přibližujeme k minimu. * **Gradientní metoda (největší spád):** * Směr je záporný gradient: %%x_{k+1} = x_k - \alpha_k \nabla f(x_k)%% * Jednoduchá, ale může **konvergovat pomalu** nebo klesat příliš „cikcak“ → závisí na volbě kroku. * 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: %%x_{k+1} = x_k - H_f(x_k)^{-1} \nabla f(x_k)%% * 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: %%x_{k+1} = x_k - \left(J^T J\right)^{-1} J^T g(x_k)%% * kde $ J $ je Jacobiho matice funkce $ g(x) $ * Gauss-Newton je zjednodušená verze Newtonovy metody, která používá jen první derivace. * **Levenberg-Marquardtova metoda:** * Kombinuje robustnost gradientní metody s rychlostí Gauss-Newtonovy * Iterace: %%x_{k+1} = x_k - \left(J^T J + \mu I\right)^{-1} J^T g(x_k)%% * Parametr $ \mu > 0 $ umožňuje plynule přecházet mezi oběma metodami * 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. ===== 6. Lokální extrémy diferencovatelných funkcí vázané rovnostmi ===== 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. Taková úloha má tvar: %%\min f(x)\quad \text{za podmínky}\quad g_1(x) = 0,\,\dots,\,g_m(x) = 0%% 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**: %%\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)%% ❓ 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: * %%\nabla_x \mathcal{L}(x^*, \lambda) = \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) = 0%% * %%g_i(x^*) = 0\quad \text{pro všechna } i = 1,\dots,m%% 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í: %%g'(x^*) v = 0%% – 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: %%H(x, \lambda) = \nabla^2_{xx} \mathcal{L}(x, \lambda)%% 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í %%z = c^{T}x%% ❓ 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 %%A\,x \ge b,\;x \ge 0%% * 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í: * 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 %%z = c^{T}x%% * 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 %%c^{T}x^{(1)} = c^{T}x^{(2)} = z^{*},%% * pak každá konvexní kombinace %%x = \alpha\,x^{(1)} + (1-\alpha)\,x^{(2)},\quad 0\le\alpha\le1,%% * 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). * = Pokud má více vrcholů stejnou hodnotu cílové funkce, optimum je libovolná jejich kombinace – tedy i celé hrany mezi nimi. * **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 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: %% \min\{\,c^{T}x \;\mid\; A\,x = b,\; x \ge 0\,\} %% Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav: 1. **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 %%a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.%% 2. **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: %%x_j = x_j^+ - x_j^-,\quad x_j^+,\,x_j^- \ge 0%% ==== 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: %%\max c^T x \equiv \min (-c)^T x%% * **Rovnosti a nerovnosti:** * Rovnost převedeme na dvě opačné nerovnosti: %%a^T x = b \equiv a^T x \le b \ \text{a} \ -a^T x \le -b%% * **Proměnné bez znaménka:** * Volná proměnná se nahradí rozdílem dvou nezáporných: %%x_i = x_i^+ - x_i^-,\quad x_i^+, x_i^- \ge 0%% * **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é: %%a_i^T x + s_i = b_i,\quad s_i \ge 0%% 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):** \[ \begin{aligned} \max\; &5\,x_{1} + 4\,x_{2}\\ \text{s podmínkami} \;&x_{1} + 2x_{2} \;\le\; 8,\\ &3x_{1} + x_{2} \;\ge\; 3,\\ &x_{1} - x_{2} \;\le\; 2,\\ &x_{1},\,x_{2} \;\ge\; 0. \end{aligned} \] **Kanonický tvar (min):** \[ \begin{aligned} \min\;&-\,5\,x_{1} \;-\; 4\,x_{2}\\ \text{s podmínkami} \;&x_{1} \;+\; 2\,x_{2} \;+\; s_{1} = 8,\\ &3\,x_{1} \;+\; x_{2} \;-\; s_{2} = 3,\\ &x_{1} \;-\; x_{2} \;+\; s_{3} = 2,\\ &x_{1},\,x_{2},\,s_{1},\,s_{2},\,s_{3} \;\ge\; 0. \end{aligned} \] === Typické použití LP === 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: * **Plánování výroby a alokace zdrojů** * Např. maximalizace zisku z produktů nebo minimalizace nákladů. * Omezující podmínky mohou být kapacity strojů, pracovní doba, množství surovin apod. * **Směrování a toky v síti** * Minimalizace nákladů na přepravu v dopravní síti. * Omezení tvoří kapacity hran a požadavky na vstup/výstup v uzlech. * **Transportní a přiřazovací problémy** * Např. optimální distribuce zboží ze skladů do prodejen. * Přiřazování pracovníků k úkolům nebo trasám. * **Dietní problém** * Hledání nejlevnější kombinace potravin splňující výživové normy. * 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):** * %%\min \|A x - b\|_1 = \sum_{i=1}^m |a_i^T x - b_i|%% ❓ * **∞-norma (maximální odchylka):** * %%\min \|A x - b\|_\infty = \max_{i=1,\dots,m} |a_i^T x - b_i|%% ❓ 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: %% \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|. %% * Formulujeme ekvivalentně: %% \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}.%% 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) == * Chceme minimalizovat součet absolutních odchylek: %%\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|.%% * Formulujeme ekvivalentně:%%\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.%% * 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∞ === Mějme matice a vektory: \[ A = \begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 3 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \\ 4 \\ 7 \end{pmatrix}. \] Chceme nalézt $x = (x_{1}, x_{2})$ minimalizující $\|A\,x - b\|_{1}$. === Formulace v L₁-normě (jako LP) - Bonus === \[ \min_{x_{1},x_{2}} \;\sum_{i=1}^{3} \bigl|\,a_{i}^{T}x - b_{i}\bigr| \;\;\equiv\;\; \min_{x_{1},x_{2},\,u_{1},u_{2},u_{3}}\;u_{1} + u_{2} + u_{3} \] za podmínek (každá absolutní hodnota $\lvert a_{i}^{T}x - b_{i}\rvert \le u_{i}$): \[ \begin{cases} x_{1} \;+\; 2\,x_{2} \;-\; 5 \;\le\; u_{1},\\ -(x_{1} \;+\; 2\,x_{2} \;-\; 5) \;\le\; u_{1},\\ 2\,x_{1} \;-\; x_{2} \;-\; 4 \;\le\; u_{2},\\ -\bigl(2\,x_{1} \;-\; x_{2} \;-\; 4\bigr) \;\le\; u_{2},\\ 3\,x_{1} \;+\; x_{2} \;-\; 7 \;\le\; u_{3},\\ -\bigl(3\,x_{1} \;+\; x_{2} \;-\; 7\bigr) \;\le\; u_{3},\\ u_{1},\,u_{2},\,u_{3} \;\ge\; 0,\quad x_{1},\,x_{2} \;\text{volné (neomezené).} \end{cases} \] Protože $x_{1}, x_{2}$ jsou volné (nemají $\ge0$ omezení), převedeme je na rozdíl dvou nezáporných: \[ x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+}\ge0,\;x_{j}^{-}\ge0,\quad j=1,2. \] Pak dostaneme úplné LP: \[ \begin{aligned} \min\;&u_{1} + u_{2} + u_{3}\\ \text{s podmínkami}&\\ & (x_{1}^{+} - x_{1}^{-}) \;+\; 2\,(x_{2}^{+} - x_{2}^{-}) \;-\; 5 \;\le\; u_{1},\\ &-\bigl[(x_{1}^{+} - x_{1}^{-}) \;+\; 2\,(x_{2}^{+} - x_{2}^{-}) \;-\; 5\bigr] \;\le\; u_{1},\\ &2\,(x_{1}^{+} - x_{1}^{-}) \;-\; (x_{2}^{+} - x_{2}^{-}) \;-\; 4 \;\le\; u_{2},\\ &-\bigl[2\,(x_{1}^{+} - x_{1}^{-}) \;-\; (x_{2}^{+} - x_{2}^{-}) \;-\; 4\bigr] \;\le\; u_{2},\\ &3\,(x_{1}^{+} - x_{1}^{-}) \;+\; (x_{2}^{+} - x_{2}^{-}) \;-\; 7 \;\le\; u_{3},\\ &-\bigl[3\,(x_{1}^{+} - x_{1}^{-}) \;+\; (x_{2}^{+} - x_{2}^{-}) \;-\; 7\bigr] \;\le\; u_{3},\\ &x_{1}^{+},\,x_{1}^{-},\,x_{2}^{+},\,x_{2}^{-},\,u_{1},\,u_{2},\,u_{3} \;\ge\; 0. \end{aligned} \] === Formulace v L∞-normě (jako LP) - Bonus === \[ \min_{x_{1},x_{2}} \;\|A\,x - b\|_{\infty} \;\;\equiv\;\; \min_{x_{1},x_{2},\,t}\;t \] za podmínek: \[ \begin{cases} -\,t \;\le\; x_{1} + 2\,x_{2} \;-\; 5 \;\le\; t,\\ -\,t \;\le\; 2\,x_{1} - x_{2} \;-\; 4 \;\le\; t,\\ -\,t \;\le\; 3\,x_{1} + x_{2} \;-\; 7 \;\le\; t,\\ x_{1},\,x_{2} \;\text{volné},\quad t \;\ge\; 0. \end{cases} \] Opět nahradíme volné $x_{1},x_{2}$ jako rozdíl dvou nezáporných: \[ x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+},\,x_{j}^{-} \ge 0,\quad j=1,2. \] Pak kompletní LP v L∞-normě: \[ \begin{aligned} \min\;&t\\ \text{s podmínkami}&\\ &-\;t \;\le\; (x_{1}^{+} - x_{1}^{-}) + 2\,(x_{2}^{+} - x_{2}^{-}) - 5 \;\le\; t,\\ &-\;t \;\le\; 2\,(x_{1}^{+} - x_{1}^{-}) - (x_{2}^{+} - x_{2}^{-}) - 4 \;\le\; t,\\ &-\;t \;\le\; 3\,(x_{1}^{+} - x_{1}^{-}) + (x_{2}^{+} - x_{2}^{-}) - 7 \;\le\; t,\\ &x_{1}^{+},\,x_{1}^{-},\,x_{2}^{+},\,x_{2}^{-},\,t \;\ge\; 0. \end{aligned} \] V obou případech (L₁ i L∞) dostaneme LP, které lze řešit metodami simplex či interiér bodu. === Řešení lineárního programu (stručně) === Po převedení LP do kanonického (rovnicového) tvaru %%\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},%% ř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** * Všechny vrcholy polyedru odpovídají základním řešením soustavy $A x = b$, kde $x \ge 0$. * Pro malé problémy (2D, 3D) lze vrcholy zjistit graficky jako průsečíky omezení. * 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)** * 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). * V každém kroku vybíráme bázové proměnné a aktualizujeme tzv. simplexovou tabulku. * Algoritmus konverguje k optimu v konečně mnoha krocích, pokud nenastane degenerace. * **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í: %%\lambda x + (1-\lambda)y \in C%%❓ * Ekvivalentně: obsahuje všechny **konvexní kombinace** svých bodů, tedy výrazy ve tvaru: %%x = \sum_{i=1}^{k} \alpha_i x_i,\quad \alpha_i \ge 0,\quad \sum \alpha_i = 1%%❓ * 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: %%P = \{x \in \mathbb{R}^n \mid A x \ge b\}%%❓ * 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: %%x = \lambda x_1 + (1-\lambda) x_2,\quad \lambda \in (0,1)%%❓ * 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**: %%H = \{x \in \mathbb{R}^n \mid c^T x = c^T x^*\}%% ❓ ===== 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: %%\min\{\,c^T x \mid A x \ge b,\; x \ge 0\,\}%% K ní přísluší duální úloha: %%\max\{\,b^T y \mid A^T y \le c,\; y \ge 0\,\}%% * 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í: %%c^T x \ge b^T y%%❓ * Duální hodnota je tedy **dolní mez** primalu. * Pokud se stane, že: %%c^T x = b^T y%% * 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í: %%c^T x^* = b^T y^*%%❓ * 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$: %%x_i > 0 \;\Rightarrow\; (A^T y)_i = c_i%% * Pro každé $j$: %%y_j > 0 \;\Rightarrow\; (A x)_j = b_j%% * Obecně: %%(c_i - (A^T y)_i) \cdot x_i = 0,\quad ((A x)_j - b_j) \cdot y_j = 0%%❓ * 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í: %%f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda) f(y)%% ❓ * 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: %%\mathrm{epi}(f) = \{ (x,t) \in \mathbb{R}^n \times \mathbb{R} \mid f(x) \le t \}%% ❓ * **Subkontura (sublevel množina)** – množina všech bodů, kde funkce nepřesahuje danou hodnotu: %%\{x \in \mathbb{R}^n \mid f(x) \le \alpha \}%% ❓ ==== Podmínky konvexity podle derivací ==== Pokud je $f$ diferencovatelná: * **1. derivace – gradientová podmínka:** Funkce $f$ je konvexní ⇔ platí: %%f(y) \ge f(x) + \nabla f(x)^T (y - x)%% ❓ Pokud je $f$ dvakrát diferencovatelná: * **2. derivace – Hessova podmínka:** Funkce $f$ je konvexní ⇔ její Hessova matice je pozitivně semidefinitní: %%\nabla^2 f(x) \succeq 0\quad \text{(pro všechna } x)%% ❓ ==== Úloha konvexní optimalizace ==== * Obecná úloha konvexní optimalizace má tvar: %%\min f(x) \quad \text{za podmínek } x \in C%% * 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í.