Metoda gradientu prostego


Metoda gradientu prostego w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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.

Spis treści

Algorytm | edytuj kod

Ilustracja działania metody gradientu prostego. Widoczne są pierwsze 4 kroki algorytmu dla dwuwymiarowej funkcji celu.

Zadanie | edytuj kod

Metoda gradientu prostego 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 | edytuj kod

Na samym początku algorytmu wybierany jest punkt startowy x 0 D . {\displaystyle \mathbf {x_{0}} \in D.} W punkcie tym obliczany jest kierunek poszukiwań d k D . {\displaystyle \mathbf {d_{k}} \in D.} Punkt w następnym kroku obliczany jest według wzoru:

x k + 1 = x k + α k d k , {\displaystyle \mathbf {x_{k+1}} =\mathbf {x_{k}} +\alpha _{k}\mathbf {d_{k}} ,}

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 f ( x k ) . {\displaystyle -\nabla f(\mathbf {x_{k}} ).}

Współczynnik α k {\displaystyle \alpha _{k}} jest współczynnikiem długości kolejnych kroków. W wielu przypadkach przyjmuje się stałe niewielkie wartości:

α k = α = const . {\displaystyle \alpha _{k}=\alpha ={\textrm {const}}.}

Jeśli f {\displaystyle f} jest funkcją kwadratową o dodatnio określonym hesjanie H {\displaystyle H} to można przyjąć:

0 < α < 1 λ . {\displaystyle 0<\alpha <{\frac {1}{\lambda }}.}

gdzie λ {\displaystyle \lambda } jest największą wartością własną macierzy H . {\displaystyle H.}

Współczynnik α k {\displaystyle \alpha _{k}} może również dynamicznie zmieniać się podczas procesu szukania minimum. Kolejne kroki w algorytmie powinny być wybierane tak aby:

f ( x 0 ) > > f ( x k ) > f ( x k + 1 ) . {\displaystyle f(\mathbf {x_{0}} )>\dots >f(\mathbf {x_{k}} )>f(\mathbf {x_{k+1}} ).}

Jeżeli warunek ten nie jest w danym kroku spełniony, to należy powtórzyć krok z mniejszą wartością α k . {\displaystyle \alpha _{k}.}

Algorytm ogólnie można zapisać:

  1. Wybierz punkt startowy x 0 . {\displaystyle \mathbf {x_{0}} .}
  2. x k + 1 = x k α k f ( x k ) . {\displaystyle \mathbf {x_{k+1}} =\mathbf {x_{k}} -\alpha _{k}\nabla f(\mathbf {x_{k}} ).}
  3. Sprawdź kryterium stopu, jeśli jest spełniony to STOP.
  4. Jeżeli f ( x k + 1 ) f ( x k ) {\displaystyle f(\mathbf {x_{k+1}} )\geqslant f(\mathbf {x_{k}} )} to zmniejsz wartość α k {\displaystyle \alpha _{k}} i powtórz punkt 2 dla kroku k {\displaystyle k} -tego.
  5. Powtórz punkt 2 dla następnego kroku ( k + 1 ) . {\displaystyle (k+1).}

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

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

Zbieżność | 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 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}} \|.}

Przykład | edytuj kod

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

F ( x , y ) = sin ( 1 2 x 2 1 4 y 2 + 3 ) cos ( 2 x + 1 e y ) . {\displaystyle F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos(2x+1-e^{y}).}

Zobacz też | edytuj kod

Bibliografia | edytuj kod

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

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "Metoda gradientu prostego" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy