Gradientní sestup

Gradientní sestup (anglicky gradient descent) je iterativní optimalizační algoritmus prvního řádu pro nalezení lokálního minima diferencovatelné funkce. Myšlenkou metody je posouvat se z výchozího bodu po krocích vždy v opačném směru gradientu (nebo přibližného gradientu) funkce v daném bodě, protože to je směr nejstrmějšího klesání její hodnoty. Naopak krokování ve směru gradientu povede k lokánímu maximu této funkce; postup je pak známý jako gradientní výstup.

Algoritmus se přičítá Cauchymu, který ho poprvé zmínil v roce 1847, ale jeho konvergenční vlastnosti pro nelineární optimalizační problémy byly poprvé studovány Haskellem Currym v roce 1944.

Popis

Gradientní sestup a vrstevnice minimalizované funkce

Gradientní sestup je založen na pozorování, že pokud je funkce více proměnných $F(\mathbf {x} )$ definována a diferencovatelná v sousedství bodu $\mathbf {a}$, pak $F(\mathbf {x} )$ klesá nejrychleji, pokud se jde z $\mathbf {a}$ ve směru záporného gradientu $F$ v $\mathbf {a} ,-\nabla F(\mathbf {a} )$ . Z toho vyplývá, že se v řadě iterací z $\mathbf {a_{n}}$ posuneme k nižší hodnotě funkce $F(\mathbf {x} )$ v bodě $\mathbf {a_{n+1}} ,$ pokud

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})$

pro $\gamma \in \mathbb {R} _{+}$ dost malé, aby platilo $F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )$. Jinými slovy člen $\gamma \nabla F(\mathbf {a} )$ odčítáme od $\mathbf {a}$, protože se chceme pohybovat proti nejstrmějšímu nárůstu směrem k lokálnímu minimu. Vyjděme tedy z libovolného (náhodně nebo záměrně zvoleného) bodu $\mathbf {x} _{0}$, v němž je $F$ definovaná a diferencovatelná, a zvažujme posloupnost $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ definovanou jako

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

Ta odpovídá monotónní posloupnosti

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

takže lze doufat, že $(\mathbf {x} _{n})$ dokonverguje k nějakému lokálnímu minimu $F$ (pokud nebude divergovat k mínus nekonečnu, což by znamenalo nalezení globálního infima $F$). Všimněte si, že hodnota velikosti kroku $\gamma$ se může měnit při každé iteraci. S určitými předpoklady o funkci $F$ - například $F$ lokálně konvexní a $\nabla F$ lipschitzovská - a o algoritmu výběru $\gamma$ - např. Barzilai-Borweinovou metodou

$\gamma _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{T}\left[\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right\|^{2}}}$

lze zaručit konvergenci na lokální minimum. Pokud je funkce $F$ konvexní, lze zaručit nalezení globálního řešení.

Gradientní sestup funguje v prostorech libovolné dimenze, dokonce i v nekonečněrozměrných prostorech. V tom případě se obvykle prohledává nějaký prostor funkcí a počítá se Fréchetova derivace funkcionálu, který se má minimalizovat, aby se určil směr sestupu.