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


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


===== Optimální proložení bodů podprostorem (PCA) =====

**Motivace:** Ve strojovém učení nebo klasifikaci často pracujeme s daty ve velmi vysoké dimenzi (např. tisíce či miliony rysů). PCA a SVD umožňuje „zcvrknout“ tyto rozměry na menší podprostor tak, aby se zachoval co největší rozptyl (informace) – usnadní to vizualizaci, zrychlí algoritmy a sníží šum.

PCA lze chápat dvojím způsobem:

**1. Minimální vzdálenost od podprostoru:**
  
Hledáme ortonormální matici \(X\in\mathbb{R}^{m\times k}\) tak, aby  
%%<mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>%%  
<abbr title="promítá data na k-dimenzionální podprostor a minimalizuje součet čtverců reziduí">❓</abbr>

**2. Maximální zachycený rozptyl (stopa):**  

Volíme \(X\) tak, aby projekce dat na podprostor měla co největší celkový rozptyl, tj.  
%%<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>

=== Funkce stopa (trace) ===

Stopa matice \(A\in\mathbb{R}^{n\times n}\) je součet jejích 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 je invariantní vůči podobnosti">❓</abbr>

=== Výpočet PCA (kuchařka) s příkladem ===
1. Spočtěte matici kovariancí  
%%<mjax>S = A\,A^{T}</mjax>%%
  
2. Najděte spektrální rozklad  
%%<mjax>S = V\,\Lambda\,V^{T},\quad \lambda_{1}\ge\cdots\ge\lambda_{m}</mjax>%%  

3. Rozdělte ortonormální bázi \(V = [\,X\mid Y\,]\) 
 
4. Projekce dat na \(k\)-rozměrný podprostor:  
%%<mjax>\widehat A = X\,X^{T}A</mjax>%% 
 
5. Chyba proložení:  
%%<mjax>\|A-\widehat A\|_{F}^{2} = \sum_{i=k+1}^{m}\lambda_{i}</mjax>%%  

**Příklad pro**  
%%<mjax>A = \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix},\;k=1.</mjax>%%  
- %%<mjax>S = AA^{T} = \begin{pmatrix}5 & 4\\4 & 5\end{pmatrix}</mjax>%%  
- Eigen: %%<mjax>\lambda_{1}=9,\;\lambda_{2}=1, \;v_{1}=\tfrac1{\sqrt2}\!\begin{pmatrix}1\\1\end{pmatrix}</mjax>%%  
- %%<mjax>X = [v_{1}]\,,\quad \widehat A = X X^{T}A
= \tfrac12\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>%%  
- Chyba proložení: %%<mjax>\|A-\widehat A\|_{F}^{2} = \lambda_{2} = 1</mjax>%%  

  * **Interpretace:** PCA hledá chybu, kterou uděláme, když z matice \(A\) zahodíme \(m-k\) dimenzí a data optimálně promítneme do podprostoru dimenze \(k\). Tato chyba je dána součtem čtverců „Zahozených“ singulárních čísel:

===== Singulární rozklad matice (SVD) =====

**Definice:** Pro libovolnou matici \(A\in\mathbb{R}^{m\times n}\) existují ortogonální matice  
\(U\in\mathbb{R}^{m\times m}\), \(V\in\mathbb{R}^{n\times n}\) a diagonální matice  
\(\Sigma\in\mathbb{R}^{m\times n}\) se singulárními čísly  
\(s_{1}\ge s_{2}\ge\cdots\ge s_{p}\ge0\) \((p=\min\{m,n\})\),  
že  
%%<mjax>A = US V^{T}</mjax>%%  
<abbr title="U, V mají ortonormální sloupce (levé a pravé singulární vektory), S obsahuje singulární čísla">❓</abbr>

**Výpočet SVD:**

1. Spočtěte matice  
%%<mjax>AA^{T}=U\,S\,U^{T},\quad A^{T}A=V\,S\,V^{T}</mjax>%%  
<abbr title="S je diagonální matice s_i^2, vlastní čísla AAᵀ a AᵀA">❓</abbr>

2. Sloupce U jsou vlastní vektory matice \(AA^{T}\), sloupce V vlastní vektory \(A^{T}A\). 
 
3. Singulární čísla \(s_{i}=\sqrt{S_{ii}}\).
 
===Eckart–Youngova věta===

Nechť \(A\in\mathbb{R}^{m\times n}\), \(p=\min\{m,n\}\) a \(k\le p\). Řešením úlohy  
%%<mjax>\min_{\mathrm{rank}(B)\le k}\|A - B\|_{F}^{2}</mjax>%%  
je matice  
%%<mjax>
B^{*}
= U\,S_{k}\,V^{T}
= \sum_{i=1}^{k} s_{i}\,u_{i}\,v_{i}^{T}
</mjax>%%  

kde  
%%<mjax>
S_{k}
= \mathrm{diag}(s_{1},\dots,s_{k},0,\dots,0)\in\mathbb{R}^{p\times p}
</mjax>%%  

**Aplikace SVD:**  
  * Data-redukce, PCA  
  * Řešení nesingulárních či přeurčených soustav  
  * Komprese obrázků (low-rank aproximace)  
  * Výpočet pseudoinverzí a regularizace  

===== Globální a lokální extrémy funkce na podmnožině ℝⁿ =====

Nechť \(f: D \subseteq \mathbb{R}^{n} \to \mathbb{R}\), kde \(D\) je podmnožina ℝⁿ.

=== Definice globálních a lokálních extrémů ===
  * **Globální minimum**:

bod \(x^{*}\in D\) je globální minimum, pokud  
%%<mjax>f(x^{*}) \le f(x)\quad \forall\,x\in D.</mjax>%%  
  * **Globální maximum**:

bod \(x^{*}\in D\) je globální maximum, pokud  
%%<mjax>f(x^{*}) \ge f(x)\quad \forall\,x\in D.</mjax>%%  
  * **Lokální minimum**:

bod \(x^{*}\in D\) je lokální minimum, pokud existuje otevřené okolí \(U \subset D\) takové, že  
%%<mjax>f(x^{*}) \le f(x)\quad \forall\,x\in U.</mjax>%%  
  * **Lokální maximum**:

bod \(x^{*}\in D\) je lokální maximum, pokud existuje otevřené okolí \(U \subset D\) takové, že  
%%<mjax>f(x^{*}) \ge f(x)\quad \forall\,x\in U.</mjax>%%  

Pokud je \(f\) konvexní na celém oboru \(D\), pak lokální minimum je zároveň globálním minimem; obdobně pokud je \(f\) konkávní, pak lokální maximum je globálním maximem.

Pro nalezení lok min a max použijeme Hessovu matici a nulové první derivace.
 
===== 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: • b4b35psr • b4b17eam • b4b36pdv • b4b32pks • b0b01pst • b6b36omo • b6b36ts1 • b0b35apo • b0b39pgr • b0b01lgr
Search

Navigation

Print/export

Tools

QR Code
