Tekst źródłowy strony Metoda najszybszego spadku

{{Dopracować|źródła = 2023-06}}
'''Metoda najszybszego spadku''' – [[metoda numeryczna|algorytm numeryczny]] mający na celu znalezienie [[Ekstremum funkcji|minimum]] zadanej [[Funkcja celowa|funkcji celu]].

Metoda najszybszego spadku jest modyfikacją [[metoda gradientu prostego|metody gradientu prostego]].

== Algorytm ==
=== Zadanie ===
Metoda najszybszego spadku jest iteracyjnym algorytmem wyszukiwania [[Ekstremum funkcji|minimum]] zadanej funkcji celu <math>f{:}</math>
: <math>f \colon D \mapsto \mathbb{R},</math>

gdzie <math>D \subset \mathbb{R}^n.</math>

Założenia dla metody są następujące:
:* <math>f \in \mathrm{C}^1</math> (funkcja jest [[funkcja ciągła|ciągła]] i [[funkcja różniczkowalna|różniczkowalna]]),
:* <math>f</math> jest ściśle [[Wypukłość funkcji|wypukła]] w badanej dziedzinie.

=== Opis ===
[[Plik:Metoda najszybszego spadku.svg|thumb|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 <math>\mathbf{x_0} \in D.</math> W punkcie tym obliczany jest [[Gradient (matematyka)|antygradient]] <math>-\nabla f(\mathbf{x_k})</math> funkcji celu, który będzie stanowił kierunek poszukiwań w procedurze. Następny punkt jest obliczany według wzoru:
: <math>\mathbf{x_{k+1}} = \mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k}),</math>

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 <math>\alpha_k</math> – dokonywana jest minimalizacja kierunkowa funkcji:
: <math>f(\mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k}) ) = \min_{\alpha > 0} f(\mathbf{x_k} - \alpha \nabla f(\mathbf{x_k})).</math>

[[Algorytm]] ogólnie można zapisać:
# Wybierz punkt startowy <math>\mathbf{x_0}.</math>
# Dokonaj minimalizacji kierunkowej funkcji <math>f(\mathbf{x_k} - \alpha \nabla f(\mathbf{x_k}) )</math> względem <math>\alpha.</math>
# <math>\mathbf{x_{k+1}} = \mathbf{x_k} - \alpha_k \nabla f(\mathbf{x_k}).</math>
# 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 (optymalizacja)|metoda Newtona]].

=== Kryterium stopu ===
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 <math>\epsilon</math> oraz normy <math>\|{\cdot}\|</math>):
* <math>\|\nabla f(\mathbf{x_k})\| \leqslant \epsilon</math> (test stacjonarności),
* <math>\|\mathbf{x_{k+1}} - \mathbf{x_k}\| \leqslant \epsilon.</math>

=== Zbieżność ===
[[Plik:Metoda najszybszego spadku - wady.svg|thumb|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ść|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 <math>\mathbf{x}^*</math> maleją liniowo:
: <math>\|\mathbf{x}^* - \mathbf{x_{k+1}}\| \leqslant c\|\mathbf{x}^* - \mathbf{x_k}\|.</math>

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ż ==
* [[metoda gradientu prostego]]
* [[metoda Newtona (optymalizacja)|metoda Newtona]]
* [[metoda złotego podziału]]
* [[Optymalizacja (matematyka)|optymalizacja]]

== Bibliografia ==
* {{Cytuj książkę |autor = Fortuna Z. |autor3 = Macukow B. |autor2 = Wąsowski J. |tytuł = Metody numeryczne |wydawca = Wydawnictwa Naukowo-Techniczne |rok = 2006 |isbn = 83-204-3245-6 |wydanie= 7, dodr}}
* {{Cytuj książkę |autor = Stachurski A. |autor2 = Wierzbicki A. |tytuł = Podstawy optymalizacji |wydawca = Oficyna Wydawnicza PW |rok = 1999 |isbn = 83-7207-085-7}}

== Linki zewnętrzne ==
* [http://optymalizacja.w8.pl/NajszybszegoSpadku.html Metoda najszybszego spadku]
* [http://www.isep.pw.edu.pl/~ambor/Pomoce/gradientowe.htm Metody gradientowe optymalizacji statycznej]

{{Kontrola autorytatywna}}

[[Kategoria:Metody numeryczne]]
[[Kategoria:Metody optymalizacji]]