Metoda najszybszego spadku

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Metoda najszybszego spadku jest modyfikacją metody gradientu prostego.

Algorytm[edytuj | edytuj kod]

Zadanie[edytuj | edytuj kod]

Metoda najszybszego spadku 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]

Ilustracja działania metody najszybszego spadku dla dwuwymiarowej funkcji celu. W każdym kroku, w zadanym kierunku wyszukiwana jest najmniejsza wartość funkcji celu.

Działanie metody najszybszego spadku jest bardzo podobne do metody gradientu prostego. Na samym początku algorytmu wybierany jest punkt startowy \mathbf{x_0} \in D. W punkcie tym obliczany jest antygradient \displaystyle -\nabla f(\mathbf{x_k}) funkcji celu, który będzie stanowił kierunek poszukiwań w procedurze. Następny punkt jest obliczany według wzoru:

\mathbf{x_{k+1}} = \mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k})

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

Różnicą pomiędzy metodą najszybszego spadku, a metodą gradientu prostego jest sposób wyszukiwania wartości \alpha_k - dokonywana jest minimalizacja kierunkowa funkcji:

f(\mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k}) ) = \min_{\alpha > 0} f(\mathbf{x_k} - \alpha \nabla f(\mathbf{x_k}) )

Algorytm ogólnie można zapisać:

  1. Wybierz punkt startowy \mathbf{x_0}
  2. Dokonaj minimalizacji kierunkowej funkcji f(\mathbf{x_k} - \alpha \nabla f(\mathbf{x_k}) ) względem \alpha.
  3. \mathbf{x_{k+1}} = \mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k})
  4. Sprawdź kryterium stopu, jeśli jest spełniony to STOP. W przeciwnym wypadku powtórz punkt 2.

Metodami minimalizacji jednowymiarowej mogą być metoda złotego podziału, metoda dychotomii, metoda punktu środkowego, czy metoda Newtona.

Kryterium stopu[edytuj | edytuj kod]

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie najszybszego spadku, 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]

Przykład niefortunnego wyboru punktu startowego w metodzie najszybszego spadku. Przy takim wyborze dla odpowiedniego rodzaju funkcji celu metoda charakteryzuje się wolną zbieżnością.

Metoda najszybszego spadku 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

Metoda najszybszego spadku ma szybszą zbieżność w porównaniu z metodą gradientu prostego. Niemniej oba algorytmy należą do klasy algorytmów o złożoności liniowej.

Wadą metody jest wolna zbieżność przy niezbyt fortunnym wyborze punktu startowego. Dodatkowo metoda może być bardzo wrażliwa na błędy zaokrągleń.

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]