Metoda gradientu prostego
![]() |
Ten artykuł od 2020-10 zawiera treści, przy których brakuje odnośników do źródeł. |
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
edytujZadanie
edytujMetoda gradientu prostego jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu
gdzie
Założenia dla metody są następujące:
- (funkcja jest ciągła i różniczkowalna),
- jest ściśle wypukła w badanej dziedzinie.
Opis
edytujNa samym początku algorytmu wybierany jest punkt startowy W punkcie tym obliczany jest kierunek poszukiwań Punkt w następnym kroku obliczany jest według wzoru:
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
Współczynnik jest współczynnikiem długości kolejnych kroków. W wielu przypadkach przyjmuje się stałe niewielkie wartości:
Jeśli jest funkcją kwadratową o dodatnio określonym hesjanie to można przyjąć:
gdzie jest największą wartością własną macierzy
Współczynnik może również dynamicznie zmieniać się podczas procesu szukania minimum. Kolejne kroki w algorytmie powinny być wybierane tak aby:
Jeżeli warunek ten nie jest w danym kroku spełniony, to należy powtórzyć krok z mniejszą wartością
Algorytm ogólnie można zapisać:
- Wybierz punkt startowy
- Sprawdź kryterium stopu, jeśli jest spełniony to STOP.
- Jeżeli to zmniejsz wartość i powtórz punkt 2 dla kroku -tego.
- Powtórz punkt 2 dla następnego kroku
Kryterium stopu
edytujW 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 ):
- (test stacjonarności)
Zbieżność
edytujMetoda 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:
Przykład
edytujNa poniższych rysunkach zilustrowane zostały kolejne kroki metody gradientu prostego dla funkcji:
Zobacz też
edytujBibliografia
edytuj- Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.* Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 1999.