Metoda najszybszego spadku

Wikipedia:Weryfikowalność
 Ten artykuł od 2023-06 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Metoda najszybszego spadku – algorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.

Metoda najszybszego spadku jest modyfikacją metody gradientu prostego.

Algorytm

Zadanie

Metoda najszybszego spadku jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu f : {\displaystyle f{:}}

f : D ↦ R , {\displaystyle f\colon D\mapsto \mathbb {R} ,}

gdzie D ⊂ R n . {\displaystyle D\subset \mathbb {R} ^{n}.}

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

Opis

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 x 0 ∈ D . {\displaystyle \mathbf {x_{0}} \in D.} W punkcie tym obliczany jest antygradient − ∇ f ( x k ) {\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:

x k + 1 = x k − α k ∇ f ( x k ) , {\displaystyle \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 α k {\displaystyle \alpha _{k}} – dokonywana jest minimalizacja kierunkowa funkcji:

f ( x k − α k ∇ f ( x k ) ) = min α > 0 f ( x k − α ∇ f ( x k ) ) . {\displaystyle 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 x 0 . {\displaystyle \mathbf {x_{0}} .}
  2. Dokonaj minimalizacji kierunkowej funkcji f ( x k − α ∇ f ( x k ) ) {\displaystyle f(\mathbf {x_{k}} -\alpha \nabla f(\mathbf {x_{k}} ))} względem α . {\displaystyle \alpha .}
  3. x k + 1 = x k − α k ∇ f ( x k ) . {\displaystyle \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

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 ϵ {\displaystyle \epsilon } oraz normy ‖ ⋅ ‖ {\displaystyle \|{\cdot }\|} ):

  • ‖ ∇ f ( x k ) ‖ ⩽ ϵ {\displaystyle \|\nabla f(\mathbf {x_{k}} )\|\leqslant \epsilon } (test stacjonarności),
  • ‖ x k + 1 − x k ‖ ⩽ ϵ . {\displaystyle \|\mathbf {x_{k+1}} -\mathbf {x_{k}} \|\leqslant \epsilon .}

Zbieżność

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 x ∗ {\displaystyle \mathbf {x} ^{*}} maleją liniowo:

‖ x ∗ − x k + 1 ‖ ⩽ c ‖ x ∗ − x k ‖ . {\displaystyle \|\mathbf {x} ^{*}-\mathbf {x_{k+1}} \|\leqslant c\|\mathbf {x} ^{*}-\mathbf {x_{k}} \|.}

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ż

Bibliografia

  • Fortuna Z., Wąsowski J., Macukow B.: Metody numeryczne. Wyd. 7, dodr. Wydawnictwa Naukowo-Techniczne, 2006. ISBN 83-204-3245-6.
  • Stachurski A., Wierzbicki A.: Podstawy optymalizacji. Oficyna Wydawnicza PW, 1999. ISBN 83-7207-085-7.

Linki zewnętrzne

  • Metoda najszybszego spadku
  • Metody gradientowe optymalizacji statycznej
Encyklopedia internetowa:
  • БРЭ: 2711843