Metoda gradientu prostego

 Ten artykuł od 2020-10 zawiera treści, przy których brakuje odnośników do źródeł.
Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
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 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

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

Zadanie

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

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

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ść

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

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ż

Bibliografia

  • 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

  • https://web.archive.org/web/20170815181749/http://www.isep.pw.edu.pl/~ambor/Pomoce/gradientowe.htm