Metoda konjugovaných gradientů

Gradient je směr největšího poklesu, proto pokud můžeme počítat parciální derivace, minimalizací ve směru gradientu ušetříme $N$ kroků. Najdeme-li v daném směru minimum, je další gradient kolmý k původnímu.

Metoda největšího spádu může mít tedy podobný nedostatek jako metoda pevných směrů $\rightarrow$ velké množství malých kroků pro úzká dlouhá údolí. $\Rightarrow$ potřeba lepší volby směrů - konjugované gradienty

Pozn. Metoda využívá 1. parciálních derivací funkce $f(\vec{x})$, nepoužívá ale 2. parciální derivace.

Funkci vyjádříme ve tvaru

$$f(\vec{x}) \approx c - \vec{b}^T \vec{\delta x} + \frac{1}{2} \vec{\delta x}^T {\bf A} \vec{\delta x}$$

Najdeme-li $P_{i+1}$ minimalizací ve směru $- \nabla f(P_i)$. Pak $\nabla f(P_{i+1}) \bot \nabla f(P_i)$. Chceme směr $\vec{u}_{i+1}$ takový, že $\vec{u}_i {\bf A} u_{i+1} = 0$.

Nechť ${\bf A}$ je symetrická a pozitivně definitní v okolí minima. Nechť $\vec{g}_i$, $\vec{h}_i$ jsou posloupnosti vektorů takové, že

$$\vec{g}_{i+1} = \vec{g}_i - \lambda_i {\bf A} \vec{h}_i \qqu... ...qquad \vec{h}_{i+1} = \vec{g}_{i+1} + \gamma_i \vec{h}_i \ \ ,$$

kde

$$\lambda_i = \frac{\vec{g}_i \vec{g}_i}{\vec{g}_i {\bf A} \ve... ...{g}_{i+1} {\bf A} \vec{h}_i}{\vec{h}_i {\bf A} \vec{h}_i}\ \ .$$

Pak platí

$$\vec{g}_i \vec{g}_j = 0 \qquad {\rm a} \qquad \vec{h}_i {\bf A} \vec{h}_j = 0$$ a $$\vec{g}_i \cdot \vec{h}_j = 0 \qquad {\rm pro} \qquad j < i$$

Pro kvadratickou formu lze $\gamma_i$ a $\lambda_i$ spočítat i bez znalosti Hessovy matice A následovně

$$\!\!\!\!\!\!\!\!\!\!\!\! \gamma_i = \underbrace{\frac{\vec{g}... ...da_i = \frac{\vec{g}_i \vec{h}_i}{\vec{h}_i {\bf A} \vec{h}_i}$$

Pro kvadratickou formu není rozdíl mezi oběma způsoby stanovení $\gamma_i$, obecně je většinou výhodnější Polak-Ribierova metoda.

Při hledání minima budou vektory $\vec{g}_i = - \nabla f(P_i)$ označovat směr největšího spádu a vektory $\vec{h}_i$ směry hledání minima ve směru - bodu $P_i$.
Postup hledání minima metodou konjugovaných gradientů:

1. Počáteční odhad je $P_0$, $\vec{g}_0 = - \nabla f(P_0)$ a $\vec{h}_0 = \vec{g}_0$.
2. Minimalizací ve směru $\vec{h}_0$ získáme $P_1$.
3. Známe $P_1$ a vypočteme $\vec{g}_1 = - \nabla f(P_1)$.
4. Vypočteme
   
   $$\gamma_0 = \frac{\vec{g}_1 \vec{g}_1}{\vec{g}_0 \vec{g}_0} \... ... \vec{g}_1 - \vec{g}_0 \right) \vec{g}_1}{\vec{g}_0 \vec{g}_0}$$
   
   
   První způsob výpočtu $\gamma_0$ je Fletcher-Reevesova metoda, druhý je Polak-Ribierova metoda.
5. Vypočteme
   
   $$\vec{h}_1 = \vec{g}_{1} + \gamma_0 \vec{h}_0$$
   
   

6. Minimalizací ve směru $\vec{h}_1$ získáme bod $P_2$.
7. Opakujeme 3,4,5,6, dokud není minimum nalezeno s dostatečnou přesností.

Pozn. Z metod, které využívají gradient a nepočítají 2. parciální derivace, se často používají metody "proměnné metriky" (BFGS - Broyden-Fletcher-Goldfarb-Shanno nebo DFP - Davidon-Fletcher-Powell). Tyto metody jsou založeny na postupné aproximaci inverzní Hessovy matice.