Metoda gradientu prostego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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

Zadanie[edytuj | edytuj kod]

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:

Opis[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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)

Metoda gradientu prostego.Metoda gradientu prostego.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  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[edytuj | edytuj kod]