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   |


===== Vázané extrémy pomocí Lagrangeových multiplikátorů =====

Pokud pro funkci \(f(x)\) hledáme extrém pod podmínkami  
\[
g_{i}(x)=0,\quad i=1,\dots,m,
\]  
postupujeme následovně:

**Lagrangeova funkce:** 
 
  Definujeme  
%%<mjax>\mathcal{L}(x,\lambda) = f(x) - \sum_{i=1}^{m} \lambda_{i}\,g_{i}(x)</mjax>%%  
  kde \(\lambda = (\lambda_{1},\dots,\lambda_{m})\) jsou Lagrangeovy multiplikátory.  

**Nutné podmínky (stacionární body) na hladké části povrchu:**  

Hledáme \((x^{*},\lambda^{*})\) tak, aby  
%%<mjax>\nabla_{x}\mathcal{L}(x^{*},\lambda^{*}) = 0, g_{i}(x^{*}) = 0,\;i=1,\dots,m</mjax>%%  
<abbr title="∇ₓL=0 zajišťuje stacionaritu na povrchu definovaném rovnostmi g_i=0">❓</abbr>  

**Kontrola hranic domény (pokud je doména omezená nebo existují jiné ohraničení):** 
 
Kromě vnitřních stacionárních bodů na povrchu \(\{g_i(x)=0\}\) je třeba zkontrolovat i body, kde povrch naráží na hranici původní množiny \(D\) (např. krajní body, rohy). V těchto bodech se gradient \(\nabla_{x}\mathcal{L}\) nemusí rovnat nule, ale mohou vzniknout extrémy právě kvůli hranici. Zároveň musíme vyšetřit i původní funkci \(f(x)\) pro extrémy, které spadnou do omezení.

**Druhé řádové podmínky (určení typu extrému) na povrchu:**
  
Označme Hessian Lagrangeovy funkce vzhledem k \(x\) jako  
%%<mjax>H(x,\lambda) = \nabla^{2}_{xx}\mathcal{L}(x,\lambda).</mjax>%%  
  Pro každý kandidátní bod \(x^{*}\) (splňující \(g_i(x^{*})=0\) a případně ležící na hranici domény) zkontrolujeme definitnost zrestrikovaného Hessianu \(H(x^{*},\lambda^{*})\) na podprostoru tangentu k množině \(\{g_{i}(x)=0\}\):  
  * Pokud je zrestrikovaný Hessian pozitivně definitní, pak \(x^{*}\) je lokální minimum.  
  * Pokud je zrestrikovaný Hessian negativně definitní, pak \(x^{*}\) je lokální maximum.  
  * Jinak je \(x^{*}\) sedlovým bodem na povrchu definovaném omezeními.  
<abbr title="kontrola Hessianu na podprostoru tangentu zajišťuje, že extrém leží na povrchu omezení">❓</abbr>  

**Výběr globálního extrému na omezeném prostoru:** 
 
  Z nalezených stacionárních bodů \(x^{*}\) (na povrchu a případně na hranici domény) vybereme ty, které splňují druhé řádové podmínky pro požadovaný typ (minimum nebo maximum) a porovnáme jejich hodnoty \(f(x^{*})\). Nejmenší (nebo největší) hodnota mezi nimi je globálním extrémem na omezeném množině.  
  
===== Úloha lineárního programování (LP) =====

Lineární programování (LP) je optimalizační disciplína, ve které hledáme vektor \(x\in\mathbb{R}^n\), který minimalizuje (nebo maximalizuje) lineární cílovou funkci za předpokladu, že \(x\) splňuje soustavu lineárních omezení (nerovnic nebo rovnic).

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

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

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

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

  * **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**  
   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**  
   Každou proměnnou \(x_{j}\), která nemá nenegativní omezení, zapíšeme jako rozdíl dvou nezáporných proměnných:  
%%<mjax>x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+} \ge 0,\; x_{j}^{-} \ge 0.</mjax>%%  

=== Převod LP do kanonického tvaru (stručně) ===

**Pů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 ===  
LP se uplatňuje v mnoha oblastech, například:
  * **Plánování výroby a alokace zdrojů** – maximalizace zisku z produktů nebo minimalizace výrobních nákladů, kde \(x_j\) jsou počty vyrobených jednotek, \(A\,x \le b\) zachycuje omezení surovin, kapacit, pracovních hodin.  
  * **Směrování a toky v síti** – minimalizace nákladů na přepravu z bodu A do B s omezeními kapacit hran; LP formulace pro \emph{min-cost flow}.  
  * **Optimalizace transportních problémů (assignment, transporte, dietă)** – přiřazení zaměstnanců úkolům, sklady-prodejny-dodávky, minimální náklady na dietní plán.  

=== Přibližné řešení přeurčených soustav ===  
Uvažujme přeurčenou soustavu lineárních rovnic \(A\,x \approx b\), kde \(A\in\mathbb{R}^{m\times n}\), \(m>n\). Místo klasického minimaxu v L₂-normě (least squares) můžeme hledat řešení, které minimalizuje odchylku v jiných normách – L₁ resp. L∞. Obě formulace lze přepsat jako LP.

=== L∞-norm (max-norm) ===
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>%%
věnujeme pozornost následujícím možnostem:

  * **Vyhledání vrcholů a porovnání cílové funkce**  
  - Najdeme všechny vrcholy jako soustavu lineárních rovnic pro každou dvojici omezení a prohlásíme za optimum vrchol s maximální hodnotou.
  - **výhoda:** pro malé problémy ve 2D(3D) lze řešit graficky.
  - **Nevýhoda:** Počet vrcholů roste exponenciálně (\(\binom{n}{m}\)), takže postup je vhodný pouze pro velmi malé rozměry.

  * **Simplexová metoda (pohyb po hranách polyedru)**  
  - Namísto úplného výčtu vrcholů se pohybujeme z vrcholu na sousední vrchol, kde se hodnota cílové funkce vždy zlepšuje.  
  - Metoda prakticky najde optimální řešení ve velmi malém počtu kroků pro většinu reálných LP.  
  - **Výhoda:** Efektivní 
  - **Nevýhoda:** Může se zacyklit

===== Dualita v LP =====

===== Konvexní funkce ======
Trace: • exams • b4b38psia • b6b36ts1 • b0b01lgr • b0b39pgr
Search

Navigation

Print/export

Tools

QR Code
