Metoda gradientu prostego

Szablon:Dopracować Metoda gradientu prostego – algorytm numeryczny mający na celu znalezienie minimum lokalnego 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:D\mapsto ℝ,$

gdzie $D\subset {ℝ}^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 ${𝐱}_{\mathrm{𝟎}}\in D.$ W punkcie tym obliczany jest kierunek poszukiwań ${𝐝}_{𝐤}\in D.$ Punkt w następnym kroku obliczany jest według wzoru:

${𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}={𝐱}_{𝐤}+{\alpha }_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 $-\mathrm{\nabla }f({𝐱}_{𝐤}).$

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

${\alpha }_k=\alpha =\text{const}.$

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

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

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

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

$f({𝐱}_{\mathrm{𝟎}})>\dots >f({𝐱}_{𝐤})>f({𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}).$

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

Algorytm ogólnie można zapisać:

1. Wybierz punkt startowy ${𝐱}_{\mathrm{𝟎}}.$
2. ${𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}={𝐱}_{𝐤}-{\alpha }_k\mathrm{\nabla }f({𝐱}_{𝐤}).$
3. Sprawdź kryterium stopu, jeśli jest spełniony to STOP.
4. Jeżeli $f({𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}})⩾f({𝐱}_{𝐤})$ to zmniejsz wartość ${\alpha }_k$ i powtórz punkt 2 dla kroku $k$-tego.
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 $ϵ$ oraz normy $\Vert \cdot \Vert$):

$\Vert \mathrm{\nabla }f({𝐱}_{𝐤})\Vert ⩽ϵ,$ (test stacjonarności)

$\Vert {𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}-{𝐱}_{𝐤}\Vert ⩽ϵ.$

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 ${𝐱}^{*}$ maleją liniowo:

$\Vert {𝐱}^{*}-{𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}\Vert ⩽c\Vert {𝐱}^{*}-{𝐱}_{𝐤}\Vert .$

Przykład

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

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

• 
• 

Zobacz też

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

Bibliografia

• Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.* Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 1999.

Linki zewnętrzne

• https://web.archive.org/web/20170815181749/http://www.isep.pw.edu.pl/~ambor/Pomoce/gradientowe.htm