statnice:bakalar:b0b33opt

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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:

%%<mjax>\min_{x}\|A x - b\|_2^2</mjax>%%  
<abbr title="Hledáme parametry rovnice x, které minimalizují celkovou chybu.">❓</abbr>

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>%%  
<abbr title="Chyba A x−b je kolmá na každý sloupec matice A.">❓</abbr>

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>%%  
<abbr title="Výpočet řešení přes pseudoinverzi – levostranný tvar.">❓</abbr>

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:

%%<mjax>P = A (A^T A)^{-1} A^T</mjax>%%  
<abbr title="Projektor promítá vektor do prostoru generovaného sloupci matice A.">❓</abbr>

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

%%<mjax>\mathrm{dist}(b, \mathrm{rng}(A)) = \|b - P b\|_2</mjax>%%  
<abbr title="Odpovídá velikosti reziduální chyby při projekci.">❓</abbr>

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

%%<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>%%  
<abbr title="Matice, která z A vytvoří inverzi na pravé straně.">❓</abbr>

%%<mjax>x = A^+ b</mjax>%%  
<abbr title="Řešení s minimální normou pomocí pravé pseudoinverze.">❓</abbr>

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):  
    %%<mjax>A^+ = (A^T A)^{-1} A^T</mjax>%%  
    <abbr title="Matice, která z A vytvoří inverzi na levé straně.">❓</abbr>
  * Pravá pseudoinverze (full row rank):  
    %%<mjax>A^+ = A^T (A A^T)^{-1}</mjax>%%  
    <abbr title="Matice, která z A vytvoří inverzi na pravé straně.">❓</abbr>
  * Obecně:
    %%<mjax>x = A^+ b</mjax>%%  
    <abbr title="Řešení nejmenších čtverců s minimální normou.">❓</abbr>

==== Příklad ====

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


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

%%<mjax>A\,v = \lambda\,v</mjax>%%  
<abbr title="vlastní vektor se po aplikaci A pouze škáluje faktorem λ">❓</abbr>

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

%%<mjax>\det(A - \lambda I)=0</mjax>%%  
<abbr title="determinant matice A−λI dává polynom n-tého stupně v λ">❓</abbr>

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

==== 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ť  
%%<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>%%  

==== Spektrální rozklad ====

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

%%<mjax>A = V \Lambda V^T</mjax>%%  
<abbr title="Matice V je ortonormální matice vlastních vektorů a Λ je diagonální matice vlastních čísel">❓</abbr>

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>%%  
<abbr title="Poznámka: Matice V je ortonormální matice vlastních vektorů (z předchozího příkladu) a Λ je diagonální matice odpovídajících vlastních čísel.">❓</abbr> 


==== Kvadratické formy na \(\mathbb{R}^n\): definitnost, diagonalizace ====

Kvadratická forma je homogenní polynom druhého stupně definovaný symetrickou maticí \(A\):  
%%<mjax>f(x) = x^{T}A\,x</mjax>%%  
<abbr title="bez členů prvního řádu ani konstantního členu">❓</abbr>

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>%%  
<abbr title="ve vlastní bázi se kvadratická forma rozpadá na vážené součty čtverců složek y">❓</abbr>

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>%%  
<abbr title="použili jsme V a Λ z předchozího výpočtu vlastních vektorů a čísel">❓</abbr>


==== Kvadratické funkce na \(\mathbb{R}^n\): doplnění na čtverec ====

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)


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

%%<mjax>A = U \Sigma V^T</mjax>%%  
<abbr title="U a V jsou ortogonální matice, Σ je diagonální matice se singulárními čísly.">❓</abbr>

  * \( 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í):  
    * %%<mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>%%<abbr title="Promítáme data na podprostor a chceme co nejmenší součet kvadratických chyb.">❓</abbr>

  * **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>%%<abbr title="Hledáme k nejvýznamnějších dimenzí v datech, na kterých je součet variancí maximální">❓</abbr>

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

%%<mjax>\min_{\mathrm{rank}(B) \le k} \|A - B\|_F</mjax>%%  
<abbr title="Snažíme se najít nejlepší možnou aproximaci A pomocí matice nižší hodnosti.">❓</abbr>

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

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

=== Funkce stopa (trace) ===

Stopa čtvercové matice je součet diagonálních prvků:  
%%<mjax>\mathrm{tr}(A) = \sum_{i=1}^{n} A_{ii}</mjax>%%  
<abbr title="Stopa odpovídá součtu vlastních čísel a hraje roli v maximalizaci rozptylu.">❓</abbr>

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í:  %%<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>%%  <abbr title="Součet energií zahozených komponent – ztracený rozptyl.">❓</abbr>

=== Příklad ===

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.


===== 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 \):  %%<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ě**.

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

==== 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í:  
%%<mjax>\nabla f(x^*) = 0</mjax>%%  
<abbr title="Gradient v bodě x^* musí zmizet – žádný směr, kterým se hodnota f mění.">❓</abbr>

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



===== 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:
%%<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í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>%% <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:
  * **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**  
    - 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:

%%<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>%% 
   
   
==== Varianty zadání ====

Úlohu LP lze převádět mezi různými tvary – např. aby vyhovovala algoritmům (simplex, metoda vnitřního bodu) nebo vizualizaci.

  * **Minimalizace vs. maximalizace:**
    * Maximalizaci převedeme na minimalizaci změnou znaménka: %%<mjax>\max c^T x \equiv \min (-c)^T x</mjax>%%

  * **Rovnosti a nerovnosti:**
    * Rovnost převedeme na dvě opačné nerovnosti: %%<mjax>a^T x = b \equiv a^T x \le b \ \text{a} \ -a^T x \le -b</mjax>%%

  * **Proměnné bez znaménka:**
    * Volná proměnná se nahradí rozdílem dvou nezáporných: %%<mjax>x_i = x_i^+ - x_i^-,\quad x_i^+, x_i^- \ge 0</mjax>%%

  * **Slack proměnné (u nerovností):**
    * Každou nerovnost \(a_i^T x \le b_i\) převedeme na rovnici přidáním nové nezáporné proměnné: %%<mjax>a_i^T x + s_i = b_i,\quad s_i \ge 0</mjax>%%

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):**  
    * %%<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) ==
  * 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.

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

===== 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í.
Trace: • b0b01lgr • b4b38nvs • b4m35ko • b4m36san • exams • exams • b4m39viz • b0b35lsp • a4m33pal • b4b36zui
Search

Navigation

Print/export

Tools

QR Code
