19. Hladká optimalizace (bez vazeb), spádové metody, volba směru a délky kroku. (NI-PON)¶

Matematické základy¶

Definice totální derivace¶

Nechť máme funkci $f: D \to \mathbb{R}$ definovanou na otevřené množině $D \subset \mathbb{R}^n$ . Funkce $f$ je říkáme, že je totálně diferencovatelná v bodě $a \in D$ , pokud existuje lineární zobrazení (tzv. totální derivace) $Df(a): \mathbb{R}^n \to \mathbb{R}$ , pro které platí

$\lim_{h\to 0}\frac{\| f(a+h)-f(a) - Df(a)[h] \|}{\|h\|} = 0.$

Označení $Df(a)$ je často zapisováno jako $f'(a)$ a jeho reprezentací je gradient (pro skalární funkce).

Gradient¶

Gradient funkce $f$ , značený $\nabla f(a)$ , je vektor složený z parciálních derivací, tedy

$\nabla f(a) = \left( \frac{\partial f}{\partial x_1}(a), \frac{\partial f}{\partial x_2}(a), \dots, \frac{\partial f}{\partial x_n}(a) \right)^T.$

Gradient udává směr největšího lokálního nárůstu hodnoty funkce. Pro jakoukoli jednotkovou směrovou složku $s$ potom platí, že derivace ve směru $s$ je dána vzorcem

$\nabla_s f(a) = \nabla f(a)^T s.$

Intuitivně tedy, když se pohybujeme ve směru $\nabla f(a)$ , funkce roste nejrychleji, zatímco pohyb proti gradientu (tedy $-\nabla f(a)$ ) vede k nejstrmějšímu poklesu.

Hessianova matice¶

Hessian funkce $f$ je druhá derivace, tedy matice druhých parciálních derivací, kterou zapisujeme jako

$H(a) = \nabla^2 f(a) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2}(a) & \frac{\partial^2 f}{\partial x_1 \partial x_2}(a) & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n}(a) \\ \frac{\partial^2 f}{\partial x_2 \partial x_1}(a) & \frac{\partial^2 f}{\partial x_2^2}(a) & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n}(a) \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1}(a) & \frac{\partial^2 f}{\partial x_n \partial x_2}(a) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(a) \end{pmatrix}.$

Hessian poskytuje informaci o zakřivení funkce. Pokud je Hessian pozitivně definitní, funkce je lokálně konvexní, což v optimalizačních úlohách značí, že nalezený lokální minimální bod je také globálním minimem v okolí.

Taylorův rozvoj¶

Taylorův rozvoj používáme pro lokální aproximaci funkce. Pro funkci $f$ dvakrát spojitě diferencovatelnou v bodě $a$ a pro malý vektorový posun $p$ platí

$f(a+p) \approx f(a) + \nabla f(a)^T p + \frac{1}{2}\, p^T H(a)\, p.$

Tato aproximace umožňuje nahlédnout do chování funkce v okolí bodu $a$ – lineární člen dává informaci o sklonu (gradientu) a kvadratický člen o zakřivení (Hessianu).

Hladká optimalizace¶

Optimalizační úloha hladké optimalizace bez vazeb se formuluje následovně:

$\min_{x \in \mathbb{R}^n} f(x), $$ kde funkce $f(x)$ je hladká (tedy diferencovatelná – ideálně vícekrát). Cílem úlohy je najít takový bod $x^*$, ve kterém $f(x)$ dosahuje lokálního (či globálního) minima, což znamená, že $$ \nabla f(x^*) = 0$

Přístupy: Line search a Trust region¶

Line search (hledání podél přímky)
- Tento přístup spočívá v určení vhodného směru $p_k$ z aktuálního bodu $x_k$ a následném hledání optimální délky kroku $\alpha_k$ , aby byl proveden příznivý posun na novou aproximaci $x_{k+1} = x_k + \alpha_k p_k$ .
- Line search může hledat absolutně optimální délku kroku (tzv. exact line search), ale často se použije neexaktní přístup (např. pomocí Armijovy nebo Wolfeho podmínky), který vyžaduje menší výpočetní náklady.
Trust region (oblast důvěry)
- Místo hledání pohybu pouze v jednom směru se v tomto přístupu vytváří lokální aproximace funkce $f(x)$ (obvykle kvadratická) kolem bodu $x_k$ . Následně se hledá minimální bod této aproximace uvnitř předem definované oblasti (oblast důvěry) $\{ p \mid \|p\| \le \Delta_k \}$ . Pokud aproximace dobře odhaduje chování funkce, může být krok přijat, jinak se velikost trust region upraví.

Spádové metody¶

Spádové metody (také gradientní descent) jsou iterační algoritmy, které využívají informace o gradientu (a případně Hessianu) k hledání minima.

Metoda největšího spádu¶

Princip a intuice:

Základním principem metody největšího spádu je pohyb ve směru proti gradientu, protože tento směr představuje nejstrmější pokles funkce. Intuice je jednoduchá – pokud jste v bodě $x_k$ , pak posunem $-\nabla f(x_k)$ se rychle dostanete do oblasti, kde je funkční hodnota nižší.

Matematická formulace a algoritmus:

Vybereme počáteční bod $x_0$ a poté iterujeme podle vzorce

$x_{k+1} = x_k - \alpha_k \nabla f(x_k),$

kde $\alpha_k > 0$ představuje délku kroku. Výběr $\alpha_k$ je zásadní, jelikož příliš malý krok může vést k velmi pomalé konvergenci, zatímco příliš velký krok může způsobit přeskočení minima.

Algoritmické body:

V každé iteraci se vypočte gradient $\nabla f(x_k)$ .
Následně je vyhledána vhodná délka kroku $\alpha_k$ (viz sekce Volba směru a délky kroku).

Newtonova metoda¶

Newtonova metoda využívá druhý řád Taylorova rozvoje k aproximaci funkce $f(x)$ v okolí aktuálního bodu $x_k$ . Taylorův rozvoj se zapíše jako

$f(x_k+p) \approx f(x_k) + \nabla f(x_k)^T p + \frac{1}{2}\, p^T H(x_k) p,$

kde

$\nabla f(x_k)$ je gradient funkce v bodě $x_k$ , který udává směr největšího nárůstu,
$H(x_k)$ pak Hessian – matice druhých parciálních derivací – zachycuje zakřivení funkce.

Pro nalezení minima této kvadratické aproximace se požaduje, aby byl gradient aproximace nulový. Tedy stanovíme podmínku stacionarity:

$\nabla f(x_k) + H(x_k) p = 0.$

Řešením této lineární rovnice dostaneme posun

$p_k = -H(x_k)^{-1} \nabla f(x_k).$

Iterační schéma:

Jakmile získáme posun $p_k$ , vytvoříme novou aproximaci řešení:

$x_{k+1} = x_k + p_k.$

Tento krok se opakuje, dokud není dosaženo konvergence – typicky když je velikost gradientu nebo změna v hodnotě $x$ menší než daná tolerance.

Poznámky a omezení:

Pokud je Hessian $H(x_k)$ pozitivně definitní, směrem $p_k$ určuje příznivý pokles funkční hodnoty.
Inverze Hessianu může být výpočetně náročná, zvláště pro vysokodimenzionální problémy.
V praxi se proto často používají modifikované metody (např. kvazi-Newtonovy metody, jako BFGS), které aproximují Hessian.

Volba směru a délky kroku¶

Volba směru¶

V rámci iterační metody je nezbytné vybrat takový směr $p_k$ , aby byl garantován pokles funkční hodnoty. Podmínkou pro spádový směr je, že

$\nabla f(x_k)^T p_k < 0.$

Příklady volby směru:

Metoda největšího spádu: zvolíme $p_k = -\nabla f(x_k)$ .
Newtonův směr: volbou $p_k = -H(x_k)^{-1} \nabla f(x_k)$ se využívá zakřivení funkce, což často zaručuje rychlejší konvergenci.

Volba délky kroku¶

Existují dva základní přístupy:

Exact line search – hledáme přesnou hodnotu, která minimalizuje funkci podél směru $\alpha_k = \arg\min_{\alpha > 0} f\left(x_k + \alpha\, p_k\right)$ Tato metoda je však výpočetně náročná, jelikož vyžaduje přesné řešení jednorozměrné optimalizační podúlohy.
Inexact line search – vybíráme délku kroku tak, aby byl zajištěn dostačující pokles funkce při výrazně nižších nákladech. Tento přístup využívá podmínky (criteria), které regulují, jak velký pokles funkce by měl být dosažen a zároveň aby krok nebyl příliš malý. Níže jsou popsány tři nejpoužívanější podmínky.
- Armijova podmínka se zaměřuje především na to, aby hodnota funkce v novém bodě byla dostatečně nižší než předpovězeno lineární aproximací.
- Goldsteinova podmínka dále omezuje možnost, že krok bude příliš malý, tím že vymezuje jak dolní, tak horní mez.
- Wolfeho podmínky kromě dostatečného poklesu kontrolují také změnu gradientu, aby se zajistilo, že krok není ani příliš malý, ani příliš velký.

Armijova podmínka¶

Armijova podmínka (také nazývaná podmínka dostatečného poklesu) stanoví, že zvolený krok $\alpha_k$ musí splňovat:

$f(x_k + \alpha_k\, p_k) \leq f(x_k) + c\, \alpha_k\, \nabla f(x_k)^T p_k,$

kde $0 < c < 1$ je předem zvolená konstanta. Tato nerovnost zaručuje, že nová hodnota funkce $f$ bude pod lineární aproximací vycházející z aktuálního bodu $x_k$ .

Intuice¶

Snížení funkční hodnoty: Představte si tečnu ke grafu funkce $f$ v bodě $x_k$ . Armijova podmínka vyžaduje, aby bod $x_k + \alpha_k\, p_k$ ležel pod touto tečnou s určitou rezervou. Tím se zajistí, že krok přispívá k dostatečnému poklesu funkční hodnoty.
Omezujeme příliš malé kroky: Pokud by $\alpha_k$ bylo příliš malé, nerovnost by byla triválně splněna, ale pokrok by byl minimální. Proto se obvykle Armijovu podmínku implementuje spolu s algorithmickým postupem, který začíná s větší hodnotou $\alpha$ a následně ji postupně zmenšuje (tzv. backtracking line search).

Goldsteinova podmínka¶

Goldsteinova podmínka stanoví, že hodnota funkce v novém bodě musí ležet mezi dvěma lineárními mezemi, a to:

$f(x_k) + (1-c)\, \alpha_k\, \nabla f(x_k)^T p_k \leq f(x_k + \alpha_k\, p_k) \leq f(x_k) + c\, \alpha_k\, \nabla f(x_k)^T p_k,$

kde $0 < c < \frac{1}{2}$ .

Intuice¶

Vyváženost kroku: Horní mez (stejně jako u Armijovy podmínky) zajišťuje, že krok není příliš velký a vede ke značnému poklesu funkce.
Ochrana před příliš malými kroky: Dolní mez brání tomu, aby zvolený krok byl extrémně malý – vlastně vymezuje minimální požadavek na pokles, který musí být dosažen.
Nevýhoda: Někdy se může stát, že hledaný krok splňující obě nerovnosti může "minout" optimální hodnotu pro $\alpha_k$ ; tedy optimalizátor by mohl přijmout krok, který není téměř nejlepším možným řešením.

Wolfeho podmínky¶

Wolfeho podmínky rozšiřují Armijovu podmínku o dodatečnou kontrolu derivace, čímž se vyžaduje, aby nebyl krok příliš krátký a zároveň se udržel dostatečný pokles funkce.

Slabá Wolfeho podmínka¶

Krok $\alpha_k$ musí splňovat:

Dostatečný pokles: $f(x_k + \alpha_k\, p_k) \leq f(x_k) + c_1\, \alpha_k\, \nabla f(x_k)^T p_k$
Křivostní podmínka: $\nabla f(x_k + \alpha_k\, p_k)^T p_k \geq c_2\, \nabla f(x_k)^T p_k$

kde $0 < c_1 < c_2 < 1$ .

Intuice¶

Dostatečný pokles: První nerovnost zaručuje, že jsme se dostatečně snížili z hlediska funkční hodnoty.
Kontrola derivace: Druhá nerovnost zajišťuje, že velikost derivace (směr změny) na novém bodě není příliš malá – což by mohlo indikovat, že jsme se zastavili před příliš brzkým konvergováním nebo jsme nepokročili dále, než je nutné.

Silná Wolfeho podmínka¶

Kromě prvního požadavku, který je stejný jako u slabé Wolfeho podmínky, se přidává absolutní hodnota derivace:

$\left| \nabla f(x_k + \alpha_k\, p_k)^T p_k \right| \leq c_2\, \left| \nabla f(x_k)^T p_k \right|.$

Intuice¶

Omezení příliš velké změny derivace: Přidáním absolutní hodnoty se zajišťuje, že derivace na novém bodě není extrémně velká. To napomáhá tomu, aby krok nebyl příliš agresivní, a tak chrání algoritmus před oscilacemi nebo nestability v iteracích.
Vyvážení mezi poklesem a krokem: Silná Wolfeho podmínka efektivně vyvažuje požadavek na dostatečný pokles funkce a zároveň kontroluje, aby krok nebyl tak malý, že by brzdil konvergenci.