Przejdź do zawartości

Metoda gradientu prostego

Z Wikipedii, wolnej encyklopedii

Metoda gradientu prostegoalgorytm 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

[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

gdzie

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

Na 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ć:

  1. Wybierz punkt startowy
  2. Sprawdź kryterium stopu, jeśli jest spełniony to STOP.
  3. Jeżeli to zmniejsz wartość i powtórz punkt 2 dla kroku -tego.
  4. Powtórz punkt 2 dla następnego kroku

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 oraz normy ):

(test stacjonarności)

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 maleją liniowo:

Przykład

[edytuj | edytuj kod]

Na poniższych rysunkach zilustrowane zostały kolejne kroki metody gradientu prostego dla funkcji:

Zobacz też

[edytuj | edytuj kod]

Bibliografia

[edytuj | edytuj kod]
  • Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.* Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 1999.

Linki zewnętrzne

[edytuj | edytuj kod]