Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita.

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.

Ř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.

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:

<mjax>\min_{x}\|A x - b\|_2^2</mjax> ❓

Tato úloha je speciálním případem obecného problému minimalizace funkce: <mjax>f(x) := \|g(x)\|^2 = \sum_{i=1}^{m} g_i(x)^2</mjax> 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:

<mjax>A^T A x = A^T b</mjax> ❓

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é:

<mjax>x = (A^T A)^{-1} A^T b</mjax> ❓

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.

Ř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:

<mjax>P = A (A^T A)^{-1} A^T</mjax> ❓

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 \( b \) od podprostoru \( \mathrm{rng}(A) \) měříme jako normu vektoru chyby (reziduum):

<mjax>\mathrm{dist}(b, \mathrm{rng}(A)) = \|b - P b\|_2</mjax> ❓

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 \).

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:

<mjax>\min_{x} \|x\|_2 \quad \text{při podmínce} \quad A x = b</mjax>

Toto řešení lze získat pomocí tzv. pravé pseudoinverze:

<mjax>A^+ = A^T (A A^T)^{-1}</mjax> ❓

<mjax>x = A^+ b</mjax> ❓

Tato formulace platí, pokud má matice \( A \) plný řádkový hodnost (řádky jsou lineárně nezávislé).

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):

<mjax>A^+ = (A^T A)^{-1} A^T</mjax> ❓

• Pravá pseudoinverze (full row rank):

<mjax>A^+ = A^T (A A^T)^{-1}</mjax> ❓

• Obecně:

<mjax>x = A^+ b</mjax> ❓

Model: <mjax>f(x) = \alpha + \beta x</mjax>

Naměřená data: <mjax>(x_{i},y_{i}) = (1,2),\,(2,3),\,(3,5)</mjax>

Matice a vektor: <mjax> A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix},\quad b = \begin{pmatrix} 2 \\ 3 \\ 5 \end{pmatrix} </mjax>

Výpočty: <mjax> 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} </mjax>

Výsledné řešení: <mjax> \begin{pmatrix}\alpha\\\beta\end{pmatrix} = (A^T A)^{-1} A^T b = \begin{pmatrix}1/3 \\ 3/2\end{pmatrix} </mjax>

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 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:

<mjax>A\,v = \lambda\,v</mjax> ❓

Pro výpočet vlastních čísel řešíme charakteristickou rovnici:

<mjax>\det(A - \lambda I)=0</mjax> ❓

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: <mjax>A = Q \Lambda Q^T</mjax>
  • 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í.

Tento příklad ukazuje, jak krok za krokem nalézt vlastní čísla a odpovídající vektory.

Nechť <mjax>A = \begin{pmatrix}2 & 1 \\ 1 & 2\end{pmatrix}</mjax>

1. Charakteristická rovnice: <mjax>\det(A - \lambda I) = \det\begin{pmatrix}2-\lambda & 1 \\ 1 & 2-\lambda\end{pmatrix} = (2-\lambda)^{2} - 1 = 0</mjax> Řešení: <mjax>\lambda_{1}=3,\quad \lambda_{2}=1</mjax>

2. Vlastní prostor pro \(\lambda_{1}=3\): Řešíme <mjax>(A - 3I)\,v = 0 \quad\Longrightarrow\quad \begin{pmatrix}-1 & 1 \\ 1 & -1\end{pmatrix} \begin{pmatrix}v_{1}\\v_{2}\end{pmatrix} = 0</mjax> Odtud \(v_{1}=v_{2}\), tedy vlastní vektor může být <mjax>v^{(1)} = \begin{pmatrix}1\\1\end{pmatrix}</mjax>

3. Vlastní prostor pro \(\lambda_{2}=1\): Řešíme <mjax>(A - I)\,v = 0 \quad\Longrightarrow\quad \begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix} \begin{pmatrix}v_{1}\\v_{2}\end{pmatrix} = 0</mjax> Odtud \(v_{1} = -\,v_{2}\), vlastní vektor může být <mjax>v^{(2)} = \begin{pmatrix}1\\-1\end{pmatrix}</mjax>

Pro každou reálnou symetrickou matici \( A \) existuje ortogonální spektrální rozklad:

<mjax>A = V \Lambda V^T</mjax> ❓

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:

<mjax>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}</mjax> ❓

Kvadratická forma je homogenní polynom druhého stupně definovaný symetrickou maticí \(A\): <mjax>f(x) = x^{T}A\,x</mjax> ❓

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:

• <mjax>A \succ 0</mjax> – pozitivně definitní (\(\lambda_{i}>0\))
• <mjax>A \succeq 0</mjax> – pozitivně semidefinitní (\(\lambda_{i}\ge0\))
• <mjax>A \preceq 0</mjax> – negativně semidefinitní (\(\lambda_{i}\le0\))
• <mjax>A \prec 0</mjax> – 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:

<mjax>f(x) = y^T \Lambda y = \sum_{i=1}^n \lambda_i y_i^2</mjax> ❓

Z toho lze přímo určit, zda má forma minimum nebo maximum, a zda je extrém ostrý.

Příklad:

<mjax> 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} </mjax> ❓

Obecná kvadratická funkce má tvar:

<mjax>g(x) = x^T A x + b^T x + c</mjax>

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:

<mjax> g(x) = \sum_{k=0}^{n}\frac{1}{k!}\,D^{k}g(x^*)\bigl[x-x^*\bigr]^{k} + R_{n+1}(x), </mjax>

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^* \):

<mjax> T_{2}(x) = g(x^*) + \nabla g(x^*)^T (x - x^*) + \tfrac{1}{2} (x - x^*)^T \nabla^2 g(x^*) (x - x^*) </mjax>

Stacionární bod je: <mjax>x^* = -A^{-1} b</mjax>

Přepsání funkce: <mjax> g(x) = \tfrac{1}{2}(x - x^*)^T A (x - x^*) + \text{konst.} </mjax>

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)

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.

Každou reálnou matici \( A \in \mathbb{R}^{m \times n} \) lze zapsat ve tvaru:

<mjax>A = U \Sigma V^T</mjax> ❓

• \( 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 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í):
  • <mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>❓

• Maximalizace zachyceného rozptylu (stopa):
  • Volíme \(X\) tak, aby projekce dat na podprostor měla co největší rozptyl:
  • <mjax>\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)</mjax>❓

Tyto dva přístupy vedou ke stejnému výsledku – podprostoru generovanému prvními \(k\) vlastními vektory matice \(A A^T\).

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ě:

<mjax>\min_{\mathrm{rank}(B) \le k} \|A - B\|_F</mjax> ❓

Tato úloha má řešení dáno oříznutím SVD rozkladu \( A = U \Sigma V^T \) na prvních \( k \) složek:

<mjax> A_k = \sum_{i=1}^{k} s_i\,u_i\,v_i^T = U\,\Sigma_k\,V^T </mjax>

kde <mjax> \Sigma_k = \mathrm{diag}(s_1, \dots, s_k, 0, \dots, 0) \in \mathbb{R}^{m \times n} </mjax> 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.

Stopa čtvercové matice je součet diagonálních prvků: <mjax>\mathrm{tr}(A) = \sum_{i=1}^{n} A_{ii}</mjax> ❓

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í.

1. Spočítáme matici kovariancí: <mjax>S = A A^T</mjax>

• 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: <mjax>S = V \Lambda V^T,\quad \lambda_1 \ge \cdots \ge \lambda_m</mjax>

3. Zvolíme první \(k\) vektorů: \( V = [X \mid Y] \)

4. Projekce dat: <mjax>\widehat{A} = X X^T A</mjax>

5. Chyba projekce: <mjax>\|A - \widehat{A}\|_F^2 = \sum_{i=k+1}^m \lambda_i</mjax> ❓

Nechť: <mjax>A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\quad k = 1</mjax>

1. Kovarianční matice: <mjax>S = A A^T = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}</mjax>

2. Spektrální rozklad: <mjax>\lambda_1 = 9,\quad \lambda_2 = 1,\quad v_1 = \tfrac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}</mjax>

3. Výběr podprostoru: <mjax>X = [v_1]</mjax>

4. Projekce: <mjax>\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}</mjax>

5. Chyba proložení: <mjax>\|A - \widehat{A}\|_F^2 = \lambda_2 = 1</mjax>

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.

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ů.

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 \): <mjax>f(x) \ge f(x^*)</mjax>
• Lokální maximum: <mjax>f(x) \le f(x^*)</mjax>
• Globální minimum (na \(D\)): <mjax>f(x) \ge f(x^*)\quad\forall x \in D</mjax>
• Globální maximum: <mjax>f(x) \le f(x^*)\quad\forall x \in D</mjax>

Lokální extrém je jen „nejlepší v okolí“, zatímco globální je nejlepší v celé množině.

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.

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.

1. Volný extrém:

• Např. funkce <mjax>f(x, y) = x^2 + y^2</mjax>
• má globální minimum v bodě <mjax>x^* = (0, 0),\quad f(x^*) = 0</mjax>
• Jde o tvar trychtýře – minimum je ve středu a zároveň lokální i globální.

2. Vázaný extrém:

• Minimalizujeme <mjax>f(x, y) = x^2 + y^2</mjax>
• za podmínky <mjax>x + y = 1</mjax>
• 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í.

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.

Stacionární bod \( x^* \) je kandidát na extrém, pokud platí: <mjax>\nabla f(x^*) = 0</mjax> ❓

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í 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.

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: <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>

• 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: <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.

• 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) \)

• 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: <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

• 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.

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: <mjax>\min f(x)\quad \text{za podmínky}\quad g_1(x) = 0,\,\dots,\,g_m(x) = 0</mjax>

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ínky řešíme pomocí Lagrangeovy funkce: <mjax>\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x)</mjax> ❓

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.

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\).

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.

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.

1. Sestavíme Lagrangeovu funkci \( \mathcal{L}(x,\lambda) = f(x) + \lambda^T g(x) \).
2. Najdeme kandidátní body \( (x^*, \lambda^*) \), které splňují:
   • \( \nabla_x \mathcal{L}(x^*, \lambda^*) = 0 \)
   • \( g_i(x^*) = 0 \)
3. Zkontrolujeme druhý řád – restrikci Hessovy matice.
4. Pokud je doména omezená, zkontrolujeme i hraniční body.
5. Vybereme bod s nejlepší hodnotou \( f(x^*) \).

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.

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.)

Lineární programování (LP) pracuje s lineární cílovou funkcí <mjax>z = c^{T}x</mjax> ❓ 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 <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).
  • = Ř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 <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ů).
  • = 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 <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>
  • 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
  1. 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“.
  2. Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.

Obecná formulace (kanonický tvar v „nerovnicích“) je:

<mjax> \min\{\,c^{T}x \;\mid\; A\,x = b,\; x \ge 0\,\} </mjax>

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 <mjax>a_{i}^{T}x + u_{i} = b_{i},\quad u_{i} \ge 0.</mjax>

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: <mjax>x_j = x_j^+ - x_j^-,\quad x_j^+,\,x_j^- \ge 0</mjax>

Ú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ů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} \]

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ř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> ❓

• ∞-norma (maximální odchylka):
  • <mjax>\min \|A x - b\|_\infty = \max_{i=1,\dots,m} |a_i^T x - b_i|</mjax> ❓

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í.

• 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.

• Chceme minimalizovat součet absolutních odchylek: <mjax>\min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{1}\;=\;\min_{x}\;\sum_{i=1}^{m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|.</mjax>
• Formulujeme ekvivalentně:<mjax>\min_{x,\;\{u_{i}\}}\;\sum_{i=1}^{m}u_{i}\quad\text{za podmínek}\quad-\,u_{i} \;\le\; a_{i}^{T}x - b_{i}\;\le\; u_{i},\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.

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}\).

\[ \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} \]

\[ \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.

Po převedení LP do kanonického (rovnicového) tvaru <mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax>

ř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).

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ě.

• 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>❓

• 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>❓

• 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 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>❓

• 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.

• 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>❓

• 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> ❓

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.

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í.

• 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>❓
  • 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í.

• 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>❓

• 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é.

• 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>❓

• Jinými slovy: každá podmínka buď svazuje řešení (aktivní), nebo má nulový stínový dopad.

• 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.

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.

• 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> ❓

• Funkce je striktně konvexní, pokud nerovnost je ostrá pro \(x \ne y\).

• Konvexita znamená, že graf funkce je „ohnutý směrem nahoru“.

• 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> ❓

• 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> ❓

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> ❓

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> ❓

• 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í.