Metoda gradientu prostego

Metoda gradientu prostego jest pojęciem z zakresu optymalizacji matematycznej. Jest to algorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.

Jest to jedna z prostszych metod optymalizacji. Przykładami innych metod są metoda najszybszego spadku, czy metoda Newtona.

Algorytm

Ilustracja działania metody gradientu prostego. Widoczne są pierwsze 4 kroki algorytmu dla dwuwymiarowej funkcji celu.

Zadanie

Metoda gradientu prostego jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu $f$:

$f \colon D \mapsto \mathbb{R}$

gdzie $D \subset \mathbb{R}^n$.

Założenia dla metody są następujące:

• $f \in \mathrm{C}^1$ (funkcja jest ciągła i różniczkowalna),
• $f$ jest ściśle wypukła w badanej dziedzinie.

Opis

Na samym początku algorytmu wybierany jest punkt startowy $\mathbf{x_0} \in D$. W punkcie tym obliczany jest kierunek poszukiwań $\mathbf{d_k} \in D$. Punkt w następnym kroku obliczany jest według wzoru:

$\mathbf{x_{k+1}} = \mathbf{x_k} + \alpha_k \mathbf{d_k}$

jeśli obliczony punkt nie spełni warunku stopu algorytmu, całe postępowanie jest powtarzane.

Kierunkiem poszukiwań w metodzie gradientu prostego jest antygradient funkcji celu $\displaystyle -\nabla f(\mathbf{x_k})$.

Współczynnik $\alpha_k$ jest współczynnikiem długości kolejnych kroków. W wielu przypadkach przyjmuje się stałe niewielkie wartości:

$\displaystyle \alpha_k = \alpha = \textrm{const}$

Jeśli $f$ jest funkcją kwadratową o dodatnio określonym hesjanie $H$ to można przyjąć:

$\displaystyle 0 < \alpha < \frac{1}{\lambda}$

gdzie $\displaystyle \lambda$ jest największą wartością własną macierzy $H$.

Współczynnik $\displaystyle \alpha_k$ może również dynamicznie zmieniać się podczas procesu szukania minimum. Kolejne kroki w algorytmie powinny być wybierane tak aby:

$f(\mathbf{x_0}) > \dots > f(\mathbf{x_k}) > f(\mathbf{x_{k+1}})$

Jeżeli warunek ten nie jest w danym kroku spełniony, to należy powtórzyć krok z mniejszą wartością $\displaystyle \alpha_k$.

Algorytm ogólnie można zapisać:

1. Wybierz punkt startowy $\mathbf{x_0}$
2. $\mathbf{x_{k+1}} = \mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k})$
3. Sprawdź kryterium stopu, jeśli jest spełniony to STOP.
4. Jeżeli $\displaystyle f(\mathbf{x_{k+1}}) \geqslant f(\mathbf{x_{k}})$ to zmniejsz wartość $\displaystyle \alpha_k$ i powtórz punkt 2 dla kroku $k$-ego.
5. Powtórz punkt 2 dla następnego kroku $(k+1)$

Kryterium stopu

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie gradientu prostego, można użyć następujących kryteriów stopu (dla zadanej precyzji $\epsilon$ oraz normy $\parallel\cdot\parallel$):

• $\parallel \nabla f(\mathbf{x_k}) \parallel \leqslant \epsilon$ (test stacjonarności).
• $\parallel \mathbf{x_{k+1}} - \mathbf{x_k} \parallel \leqslant \epsilon$

Zbieżność

Metoda gradientu prostego jest metodą o zbieżności liniowej. Oznacza to, iż przy spełnieniu założeń metody, odległości pomiędzy kolejnymi przybliżeniami, a minimum funkcji $\mathbf{x^{\ast}}$ maleją liniowo:

$\parallel \mathbf{x^{\ast}} - \mathbf{x_{k+1}} \parallel \leqslant c \parallel \mathbf{x^{\ast}} - \mathbf{x_k} \parallel$

Przykład

Na poniższych rysunkach zilustrowane zostały kolejne kroki metody gradientu prostego dla funkcji:

$F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)$

Zobacz też

• optymalizacja
• metoda Newtona
• metoda najszybszego spadku
• metoda złotego podziału

Bibliografia

1. Fortuna Z., Macukow B., Wąsowski J.: Metody Numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.
2. Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

Linki zewnętrzne

• http://www.isep.pw.edu.pl/~ambor/Pomoce/gradientowe.htm