B0B33OPT Webové stránky předmětu

• Přibližné řešení lineární soustavy – ve smyslu nejmenších čtverců, normální rovnice. Ortogonální projekce na podprostor a její matice (ortogonální projektor), vzdálenost bodu od podprostoru. Řešení nedourčené lineární soustavy s nejmenší normou. Pseudoinverze.
• Vlastní čísla a vektory – reálné symetrické matice, její spektrální rozklad. Kvadratické formy na Rⁿ: definitnost, diagonalizace spektrálním rozkladem, minima a maxima. Kvadratické funkce na Rⁿ: doplnění na čtverec, minima a maxima.
• Optimální proložení bodů podprostorem (PCA) – nejbližší matice nižší hodnosti (low-rank approximation), singulární rozklad matice (SVD).
• Globální a lokální extrémy funkce na podmnožině Rⁿ – definice, příklady, volné a vázané extrémy.
• Volné lokální extrémy diferencovatelných funkcí – podmínky prvního a druhého řádu, numerické iterační metody (gradientní a Newtonova, Gauss-Newtonova a Levenberg-Marquardtova).
• Lokální extrémy diferencovatelných funkcí vázané rovnostmi – podmínka prvního řádu, pojem Lagrangeovy funkce a Lagrangeových multiplikátorů.
• Úloha lineárního programování (LP) – různé tvary úloh LP a jejich převody, typická použití LP, přibližné řešení přeurčených soustav v 1-normě a max-normě.
• Geometrie LP – konvexní množiny a mnohostěny, extremální body konvexního mnohostěnu.
• Dualita v LP – věta o slabé dualitě, o komplementaritě, věta o silné dualitě.
• Konvexní funkce – definice, podmínka prvního a druhého řádu, epigraf a subkontura. Úloha konvexní optimalizace.

Řešení lineární soustavy rovnic pomocí metody nejmenších čtverců, například při měření s chybami nebo pokud je soustava pře- nebo nedourčená (má více rovnic než neznámých nebo naopak). Pomocí projekce na podprostor a pseudoinverze hledáme řešení, které buď nejlépe odpovídá pozorovaným datům, nebo má nejmenší možnou normu.

Metoda nejmenších čtverců slouží k přibližnému řešení soustavy rovnic \( A x \approx b \), která nemá přesné řešení – typicky když je počet rovnic větší než počet neznámých (tzv. přeurčená soustava). Hledáme vektor \( x \), který co nejlépe „vysvětlí“ data \( b \) v rámci daného lineárního modelu.

Cílem je minimalizovat součet čtverců rozdílů (reziduí) mezi skutečnými a modelovanými hodnotami:

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

Tato úloha je speciálním případem obecného problému minimalizace funkce: <mjax>f(x) := \|g(x)\|^2 = \sum_{i=1}^{m} g_i(x)^2</mjax> kde \( g(x) = A x - b \) je lineární (viz obrázek).

Z první podmínky optimálního bodu (nulový gradient) odvodíme tzv. normální rovnice:

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

Pokud má \( A \) lineárně nezávislé sloupce (tzv. full column rank), je matice \( A^T A \) regulární (invertovatelná) a řešení je jednoznačné:

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

Tuto metodu lze chápat jako projekci vektoru \( b \) na podprostor generovaný sloupci \( A \). Pokud \( b \) neleží v tomto podprostoru, hledáme nejbližší bod z tohoto podprostoru.

Řešení úlohy nejmenších čtverců odpovídá kolmé projekci vektoru \( b \) do podprostoru \( \mathrm{rng}(A) \). Výsledkem projekce je vektor \( Ax \), který je co nejblíž vektoru \( b \) a zároveň leží v obrazu \( A \).

Projektor, který provádí tuto projekci, má tvar:

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

Vlastnosti projektoru:

• Symetrický: \( P = P^T \)
• Idempotentní: \( P^2 = P \)

Pro vektor \( z \) platí, že jeho projekce do podprostoru je \( P z \). Ortogonální doplněk (kolmý zbytek) je \( (I - P) z \), tedy kolik z vektoru „přebývá mimo“ podprostor.

Vzdálenost bodu \( b \) od podprostoru \( \mathrm{rng}(A) \) měříme jako normu vektoru chyby (reziduum):

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

To je přesně to, co minimalizujeme v úloze nejmenších čtverců – hledáme vektor \( Ax \), který je co nejblíže \( b \), a zároveň patří do obrazu \( A \).

Pokud je počet neznámých větší než počet rovnic, je systém nedourčený a má nekonečně mnoho řešení. Hledáme tedy takové řešení, které má nejmenší normu:

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

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

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

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

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

Pro libovolnou matici \( A \) existuje jedinečně definovaná Moore–Penroseova pseudoinverze \( A^+ \). Ta vrací buď:

• nejbližší možný obraz v případě přeurčené soustavy
• řešení s nejmenší normou v případě nedourčené soustavy - pokud je řešení více
• řeší úlohu nejmenších čtverců, pokud \( A x = b \) nemá přesné řešení

Zápisy:

• Levá pseudoinverze (full column rank):

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

• Pravá pseudoinverze (full row rank):

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

• Obecně:

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

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

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

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

Výpočty: <mjax> A^T A = \begin{pmatrix}3 & 6\\6 & 14\end{pmatrix},\quad (A^T A)^{-1} = \frac{1}{6}\begin{pmatrix}14 & -6\\-6 & 3\end{pmatrix},\quad A^T b = \begin{pmatrix}10\\23\end{pmatrix} </mjax>

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

Tato kapitola se zaměřuje na práci s kvadratickými výrazy a jejich souvislost s optimalizací. Pomocí vlastních čísel a vektorů dokážeme analyzovat chování kvadratických forem, určovat minima a maxima a převádět funkce do jednoduššího tvaru. Důležitým nástrojem je také spektrální rozklad symetrických matic, který umožňuje přímou interpretaci geometrických vlastností.

Vlastní čísla a vektory nám říkají, jak matice mění prostor – v některých směrech pouze škáluje, bez změny směru.

Vlastní číslo \(\lambda\) je skalár, pro nějž existuje nenulový vektor \(v\), takový že:

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

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

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

Vlastní čísla i vektory hrají klíčovou roli v optimalizaci a geometrické interpretaci matic. Pokud je \( A \) symetrická, má:

• reálná vlastní čísla,
• ortogonální bázi vlastních vektorů,
• spektrální rozklad ve tvaru: <mjax>A = Q \Lambda Q^T</mjax>
  • kde \( Q \) je ortogonální matice a \( \Lambda \) je diagonální.

Algebraická násobnost – počet výskytů kořene v charakteristickém polynomu. Geometrická násobnost – dimenze jádra \((A - \lambda I)\). V ideálním případě (symetrická matice) se algebraická a geometrická násobnost rovnají.

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

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

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

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

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

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

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

Spektrální rozklad přepisuje symetrickou matici $A$ jako ortogonální transformaci do diagonální podoby.

Využívá se pro:

• snadno analyzovat kvadratické formy (rozkládají se na vážené čtverce vlastních souřadnic),
• efektivně počítat funkce matice (např. mocniny nebo exponenciálu),
• numericky stabilně řešit lineární a optimalizační úlohy.

Příklad:

<mjax>V = \tfrac{1}{\sqrt{2}}\begin{pmatrix}1 & 1\\1 & -1\end{pmatrix},\;\Lambda=\begin{pmatrix}3&0\\0&1\end{pmatrix}\;\Longrightarrow\;A=V\Lambda V^{T}=\begin{pmatrix}2&1\\1&2\end{pmatrix}</mjax> ❓

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

Kvadratická forma nám říká, zda funkce roste nebo klesá v různých směrech – podle toho, jak vypadá matice \(A\).

Podle spektra (vlastních čísel) matice \( A \) rozlišujeme:

• <mjax>A \succ 0</mjax> – pozitivně definitní (\(\lambda_{i}>0\))
• <mjax>A \succeq 0</mjax> – pozitivně semidefinitní (\(\lambda_{i}\ge0\))
• <mjax>A \preceq 0</mjax> – negativně semidefinitní (\(\lambda_{i}\le0\))
• <mjax>A \prec 0</mjax> – negativně definitní (\(\lambda_{i}<0\))
• jinak indefinitní (část \(\lambda_{i}>0\), část \(\lambda_{i}<0\))

Diagonalizace kvadratické formy: Pomocí spektrálního rozkladu \( A = V \Lambda V^T \) a substituce \( y = V^T x \) dostaneme:

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

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

Příklad:

<mjax> f(x) = x^T A x = y^T \Lambda y = 3 y_1^2 + 1 y_2^2,\quad y = V^T x = \tfrac{1}{\sqrt{2}}\begin{pmatrix}x_1 + x_2 \\ x_1 - x_2\end{pmatrix} </mjax> ❓

Obecná kvadratická funkce má tvar:

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

Tato funkce obsahuje jak kvadratický, tak lineární člen – jejím cílem je najít stacionární bod a rozhodnout, zda jde o minimum, maximum nebo sedlový bod.

Doplnění na n-tý řád (Taylorův polynom):

Pro dostatečně hladkou funkci \(g:\mathbb{R}^n\to\mathbb{R}\) kolem bodu \(x^*\) platí Taylorův rozvoj až do \(n\)-tého řádu:

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

Pro hledání extrému ji přepíšeme pomocí doplnění na čtverec. Využíváme Taylorův polynom 2. řádu kolem bodu \( x^* \):

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

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

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

Minima a maxima (na otevřené množině \(\mathbb{R}^{n}\)):

• \(A \succ 0\): \(g\) je striktně konvexní ⇒ unikátní globální minimum v \(x^{*}\)
• \(A \prec 0\): \(g\) je striktně konkávní ⇒ unikátní globální maximum v \(x^{*}\)
• Jinak je \(x^{*}\) sedlovým bodem (žádný globální extrém)

Tato kapitola se věnuje metodám, které hledají nejlepší aproximaci dat v nižším rozměru. Typickým příkladem je metoda hlavních komponent (PCA), která minimalizuje ztrátu informace při promítání dat do podprostoru. Klíčovým nástrojem pro tuto úlohu je singulární rozklad matice (SVD) – univerzální technika pro analýzu struktury a „redukování“ matic.

Motivace: Ve strojovém učení nebo klasifikaci často pracujeme s daty ve velmi vysoké dimenzi (např. tisíce rysů). PCA umožňuje zmenšit rozměr na menší podprostor tak, aby se zachoval co největší rozptyl (informace). To vede k rychlejším výpočtům, nižšímu šumu a přehlednější vizualizaci.

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

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

• \( U \in \mathbb{R}^{m \times m} \) – levé singulární vektory
• \( \Sigma \in \mathbb{R}^{m \times n} \) – diagonální matice singulárních čísel
• \( V \in \mathbb{R}^{n \times n} \) – pravé singulární vektory

Singulární čísla \( \sigma_1 \ge \cdots \ge \sigma_r > 0 \) jsou druhé odmocniny vlastních čísel matic \( A A^T \) a \( A^T A \). SVD existuje pro každou reálnou (i obdélníkovou) matici.

Výpočet SVD:

• Spočteme spektrální rozklad \( A A^T = U S U^T \) a \( A^T A = V S V^T \)
• Singulární čísla \( s_i = \sqrt{S_{ii}} \)
• Pak \( A = U S^{1/2} V^T \)

PCA můžeme chápat dvěma způsoby:

• Minimalizace chyby projekce (minimální vzdálenost od podprostoru):
  • Hledáme podprostor dimenze \(k\), na který promítneme data tak, aby se minimalizoval součet čtverců vzdáleností (reziduí):
  • <mjax>\min_{X^{T}X=I}\sum_{i=1}^{n}\|a_{i}-XX^{T}a_{i}\|_{2}^{2}</mjax>❓

• Maximalizace zachyceného rozptylu (stopa):
  • Volíme \(X\) tak, aby projekce dat na podprostor měla co největší rozptyl:
  • <mjax>\max_{X^{T}X=I}\sum_{i=1}^{n}\|X^{T}a_{i}\|_{2}^{2}= \max_{X^{T}X=I}\|X^{T}A\|_{F}^{2}= \max_{X^{T}X=I}\mathrm{tr}\bigl(X^{T}A A^{T}X\bigr)</mjax>❓

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

Nechť \( A \in \mathbb{R}^{m \times n} \), \( p = \min\{m,n\} \) a \( k \le p \). Hledáme matici \( B \) hodnosti nejvýše \( k \), která je co nejblíže původní matici \( A \) ve Frobeniově normě:

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

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

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

kde <mjax> \Sigma_k = \mathrm{diag}(s_1, \dots, s_k, 0, \dots, 0) \in \mathbb{R}^{m \times n} </mjax> obsahuje jen první \( k \) singulárních čísel a zbytek nulujeme.

Používáme tedy jen první \( k \) singulárních složek z rozkladu SVD – to zaručuje nejlepší možnou aproximaci v dané dimenzi.

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

Stopu si můžeš představit jako míru „energie“ nebo rozptylu, kterou matice zachytává v prostoru – čím větší stopa, tím více informací.

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

• Matice \(S = A A^T\) je tzv. kovarianční matice, která říká, jak moc a v jakých směrech se data mění.

2. Provedeme spektrální rozklad: <mjax>S = V \Lambda V^T,\quad \lambda_1 \ge \cdots \ge \lambda_m</mjax>

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

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

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

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

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

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

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

4. Projekce: <mjax>\widehat{A} = X X^T A = \tfrac{1}{2} \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}2 & 1\\1 & 2\end{pmatrix} = \begin{pmatrix}1.5 & 1.5\\1.5 & 1.5\end{pmatrix}</mjax>

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

Interpretace: Projekce do 1D podprostoru zachová rozptyl \( \lambda_1 \), ztráta informace odpovídá \( \lambda_2 \). PCA tedy dává nejlepší možnou redukci na danou dimenzi.

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

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

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

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.

❓

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

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

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

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

1. Pokud polyedr nemá žádné vrcholy (např. neomezená směrově čtvercová množina), může optimum neexistovat (např. LP cílová funkce neklesá) nebo být dosaženo jen „v nekonečnu“.
2. Pokud je polyedr omezený a nevyprazdňuje se (existuje aspoň jeden vrchol), pak existuje alespoň jedno globální optimum v některém vrcholu.

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

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

Každou úlohu LP lze převést do tohoto rovnicového tvaru pomocí dvou úprav:

1. Přidání nezáporných slack proměnných 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ů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} \]

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.

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.

Chceme minimalizovat největší odchylku: <mjax> \min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{\infty} \;=\;\min_{x}\; \max_{i=1\dots m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|. </mjax> Formulujeme ekvivalentně: <mjax> \min_{x,\;t}\; t \quad\text{za podmínek}\quad -\,t \;\le\; a_{i}^{T}x - b_{i}\;\le\; t,\quad i=1,\dots,m,\quad t\in\mathbb{R}. </mjax>

Výsledkem je LP v proměnných \((x_1,\dots,x_n,t)\). Optimální \(x^{*}\) minimalizuje největší reziduum.

Chceme minimalizovat součet absolutních odchylek: <mjax> \min_{x\in\mathbb{R}^{n}} \,\bigl\|A\,x - b\bigr\|_{1} \;=\;\min_{x}\;\sum_{i=1}^{m} \bigl|\,a_{i}^{T}x - b_{i}\bigr|. </mjax> Formulujeme ekvivalentně: <mjax> \min_{x,\;\{u_{i}\}}\;\sum_{i=1}^{m}u_{i} \quad\text{za podmínek}\quad -\,u_{i} \;\le\; a_{i}^{T}x - b_{i}\;\le\; u_{i},\quad u_{i}\;\ge\; 0,\;i=1,\dots,m. </mjax> Nalezené \(\{u_{i}^{*}\}\) jsou pak absolutní odchylky a \(\sum_i u_i^*\) je minimální součet.

Mějme matice a vektory: \[ A = \begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 3 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \\ 4 \\ 7 \end{pmatrix}. \] Chceme nalézt \(x = (x_{1}, x_{2})\) minimalizující \(\|A\,x - b\|_{1}\).

\[ \min_{x_{1},x_{2}} \;\sum_{i=1}^{3} \bigl|\,a_{i}^{T}x - b_{i}\bigr| \;\;\equiv\;\; \min_{x_{1},x_{2},\,u_{1},u_{2},u_{3}}\;u_{1} + u_{2} + u_{3} \] za podmínek (každá absolutní hodnota \(\lvert a_{i}^{T}x - b_{i}\rvert \le u_{i}\)): \[ \begin{cases} x_{1} \;+\; 2\,x_{2} \;-\; 5 \;\le\; u_{1},\\ -(x_{1} \;+\; 2\,x_{2} \;-\; 5) \;\le\; u_{1},\\ 2\,x_{1} \;-\; x_{2} \;-\; 4 \;\le\; u_{2},\\ -\bigl(2\,x_{1} \;-\; x_{2} \;-\; 4\bigr) \;\le\; u_{2},\\ 3\,x_{1} \;+\; x_{2} \;-\; 7 \;\le\; u_{3},\\ -\bigl(3\,x_{1} \;+\; x_{2} \;-\; 7\bigr) \;\le\; u_{3},\\ u_{1},\,u_{2},\,u_{3} \;\ge\; 0,\quad x_{1},\,x_{2} \;\text{volné (neomezené).} \end{cases} \]

Protože \(x_{1}, x_{2}\) jsou volné (nemají \(\ge0\) omezení), převedeme je na rozdíl dvou nezáporných: \[ x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+}\ge0,\;x_{j}^{-}\ge0,\quad j=1,2. \] Pak dostaneme úplné LP: \[ \begin{aligned} \min\;&u_{1} + u_{2} + u_{3}\\ \text{s podmínkami}&\\ & (x_{1}^{+} - x_{1}^{-}) \;+\; 2\,(x_{2}^{+} - x_{2}^{-}) \;-\; 5 \;\le\; u_{1},\\ &-\bigl[(x_{1}^{+} - x_{1}^{-}) \;+\; 2\,(x_{2}^{+} - x_{2}^{-}) \;-\; 5\bigr] \;\le\; u_{1},\\ &2\,(x_{1}^{+} - x_{1}^{-}) \;-\; (x_{2}^{+} - x_{2}^{-}) \;-\; 4 \;\le\; u_{2},\\ &-\bigl[2\,(x_{1}^{+} - x_{1}^{-}) \;-\; (x_{2}^{+} - x_{2}^{-}) \;-\; 4\bigr] \;\le\; u_{2},\\ &3\,(x_{1}^{+} - x_{1}^{-}) \;+\; (x_{2}^{+} - x_{2}^{-}) \;-\; 7 \;\le\; u_{3},\\ &-\bigl[3\,(x_{1}^{+} - x_{1}^{-}) \;+\; (x_{2}^{+} - x_{2}^{-}) \;-\; 7\bigr] \;\le\; u_{3},\\ &x_{1}^{+},\,x_{1}^{-},\,x_{2}^{+},\,x_{2}^{-},\,u_{1},\,u_{2},\,u_{3} \;\ge\; 0. \end{aligned} \]

\[ \min_{x_{1},x_{2}} \;\|A\,x - b\|_{\infty} \;\;\equiv\;\; \min_{x_{1},x_{2},\,t}\;t \] za podmínek: \[ \begin{cases} -\,t \;\le\; x_{1} + 2\,x_{2} \;-\; 5 \;\le\; t,\\ -\,t \;\le\; 2\,x_{1} - x_{2} \;-\; 4 \;\le\; t,\\ -\,t \;\le\; 3\,x_{1} + x_{2} \;-\; 7 \;\le\; t,\\ x_{1},\,x_{2} \;\text{volné},\quad t \;\ge\; 0. \end{cases} \] Opět nahradíme volné \(x_{1},x_{2}\) jako rozdíl dvou nezáporných: \[ x_{j} = x_{j}^{+} - x_{j}^{-},\quad x_{j}^{+},\,x_{j}^{-} \ge 0,\quad j=1,2. \] Pak kompletní LP v L∞-normě: \[ \begin{aligned} \min\;&t\\ \text{s podmínkami}&\\ &-\;t \;\le\; (x_{1}^{+} - x_{1}^{-}) + 2\,(x_{2}^{+} - x_{2}^{-}) - 5 \;\le\; t,\\ &-\;t \;\le\; 2\,(x_{1}^{+} - x_{1}^{-}) - (x_{2}^{+} - x_{2}^{-}) - 4 \;\le\; t,\\ &-\;t \;\le\; 3\,(x_{1}^{+} - x_{1}^{-}) + (x_{2}^{+} - x_{2}^{-}) - 7 \;\le\; t,\\ &x_{1}^{+},\,x_{1}^{-},\,x_{2}^{+},\,x_{2}^{-},\,t \;\ge\; 0. \end{aligned} \]

V obou případech (L₁ i L∞) dostaneme LP, které lze řešit metodami simplex či interiér bodu.

Po převedení LP do kanonického (rovnicového) tvaru <mjax>\min\{\,c^{T}x \mid A\,x = b,\;x \ge 0\},</mjax> věnujeme pozornost následujícím možnostem:

• Vyhledání vrcholů a porovnání cílové funkce

1. 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.
2. výhoda: pro malé problémy ve 2D(3D) lze řešit graficky.
3. 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)

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