MO_7_gradiantowe

Antygradient kierunkiem poprawy

Jak pamiętamy, przyjęliśmy, że gradient $\nabla f$ jest wektorem wierszowym. Jego transpozycję do wektora kolumnowego oznacza się $\nabla^{\mathrm T}f$ .

Algorytm największego spadku (Cauchy'ego)

A. Cauchy zaproponował w 1847 r. algorytm wykorzystujący w podobny sposób gradient do rozwiązywania układu równań nieliniowych.

Algorytm największego spadku

Zachowanie algorytmów minimalizacji

Algorytm wykonał osiem kroków i zatrzymał się w punkcie $x^{(8)} = (2.27,\,1.12)$ w którym $||\nabla f (2.27,\, 1.12)|| = 0.09$ . Wartość funkcji celu $f (2.27,\,1.12) = 0.0062$ , a odległość $||x^{(8)} - x^o|| = 0.3$ .

Jakość rozwiązania

Nie jest to przypadek. Zatrzymanie algorytmu relatywnie daleko od punktu minimalizującego wynika z właściwości funkcji, która w sporym otoczeniu minimum zmienia się niewiele (wartość poziomicy w punkcie $x^{(3)}$ wynosi 0.09!). W konsekwencji zależności przyjęte w określeniu kryterium stopu szybko stają się niewielkie, co prowadzi do zbyt wczesnego (z punktu widzenia dokładności znalezienia punktu minimalizującego) zatrzymania algorytmu.

Dokładność

Algorytm największego spadku -Przykład

Po „dużym skoku” z punktu początkowego, generowane kierunki są coraz bardziej prostopadłe do drogi która prowadzi do minimum, kroki są coraz krótsze i ruch algorytmu ma charakter zygzaka o coraz mniejszych wahaniach.

Algorytm gradientu prostego

Jak widać nie najlepiej. Algorytm szybko zaczął „zygzakować”, potem odważnie „wyskoczył” z doliny prowadzącej do minimum, lecz po powrocie na jej dno zaczął zmierzać do celu tak drobnymi zygzakami, że przez pozostałe 960 iteracji posunął się bardzo niewiele. „Odwaga” była tu przypadkowa. Od mniej więcej szóstej iteracji funkcja minimalizowana w kierunku $f_P$ ma dwa minima lokalne, z których „dalsze” jest globalne. Do czterdziestej iteracji zastosowana metoda interpolacji kwadratowej znajdowała pierwsze minimum, w czterdziestej pierwszej – „przeskoczyła” to minimum i znalazła odległe minimum globalne. W tym przykładzie widać, że dokładna minimalizacja w kierunku może istotnie zmniejszyć ilość iteracji algorytmu największego spadku, ale nie wyeliminuje „zygzakowania".

Zbieżność praktyczna a teoretyczna

Zbieżność teoretyczna

Algorytm gradientu prostego

Dlaczego działa nieefektywnie?

Algorytm z pamięcią i bez

Algorytm optymalizacji równaniem różnicowym

Nieefektywność bo brak pamięci

Algorytm optymalizacji równaniem różnicowym

Nieefektywność bo brak pamięci

Jak wprowadzić pamięć ?

Poprawki

Gradient prosty dla funkcji kwadratowej

Prostopadłość kierunków poprawy

Kierunek ku rozwiązaniu

Kierunki sprzężone

Wektory (kierunki) Q-sprzężone

Najprostszym przykładem dwu wektorów sprzężonych są wektory prostopadłe, które są sprzężone względem macierzy jednostkowej. Trzy wektory w przestrzeni trójwymiarowej są sprzężone względem macierzy jednostkowej jeżeli każdy z nich jest prostopadły do płaszczyzny wyznaczonej przez dwa pozostałe. Zatem już w przestrzeni trójwymiarowej sprzężenie względem macierzy jednostkowej to inna własność niż prostopadłość.

Wzory (43.A) i (46.A) pozwalają więc wyznaczyć dla zadania optymalizacji o kwadratowej funkcji celu z macierzą $Q$ , posługując się tylko gradientami, kierunek sprzężony względem $Q$ z początkowym kierunkiem antygradientu.

Wyznaczanie kierunków poprawy

Wektory (kierunki) Q-sprzężone

Conjugate Gradient Method

Wzór Poljaka-Polaka-Ribiere'a

Algorytm gradientu sprzężonego

Dla zadań o kilku zmiennych zręczniej jest dokonywać odnowy co $3n$ lub co $2n$ kroków, ponieważ z odnową co $n$ kroków działanie algorytmu dla takich zadań może różnić się niewiele od działania algorytmu największego spadku.

Wzory F-R oraz P-P-R

Zbieżność algorytmu gradientu sprzężonego

Przy odpowiednio mocniejszych założeniach o funkcji wyboru oraz wymaganiu dokładnej minimalizacji w kierunku, można pokazać, że algorytm ten zbiega superliniowo do punktu minimalizującego.

Przy odpowiednio mocniejszych założeniach o funkcji wyboru oraz wymaganiu dokładnej minimalizacji w kierunku, można pokazać, że algorytm ten zbiega superliniowo do punktu minimalizującego.

Na rysunku zaznaczono kolorem zielonym „drogę” algorytmu gradientu sprzężonego z metodą interpolacji kwadratowej użytą do minimalizacji w kierunku, który wystartował z tego samego co poprzednio punktu początkowego $x^{(0)}=(0,3)$ i miał znaleźć rozwiązanie z dokładnością $\varepsilon = 0.05$ (przypominamy, że dla algorytmu gradientu prostego wybrana dokładność była 2 razy mniejsza i wynosiła 0.1). Dla porównania kroki algorytmu największego spadku zaznaczono na czerwono.
Algorytm wykonał siedem kroków i zatrzymał się w punkcie $x^{(7)} = (2.185,\,1.094)$ w którym $||\nabla f(2.185,\,1.094)||=0.02$ . Wartość funkcji celu $f (2.185,\,1.094) = 0.0012$ , a odległość proponowanego rozwiązania od punktu optymalnego jest równa

$||x^{(7)}-x^o||= 0.208$ .

Krok pierwszy z $x^{(0)}=(0,\,3)$ do $x^{(1)}=(2.70,\,1.51)$ był oczywiście taki sam jak dla metody gradientu prostego. Przejście z kroku szóstego do siódmego jest na rysunku niezauważalne, ponieważ $x^{(6)} = (2.190,\,1.090)$ . Zadanie jest dwuwymiarowe, zatem odnowa (ruch w kierunku antygradientu) nastąpiła w kroku trzecim, piątym i ostatnim – siódmym. Ponieważ punkty $x^{(2)}$ wyznaczone w drugim kroku przez oba algorytmy leżą jeszcze blisko siebie to i antygradienty są prawie równe, więc ruch obu algorytmów w trzecim kroku musi dać punkty $x^{(3)}$ , które też będą leżały blisko siebie. Lecz antygradient policzony w punkcie $x^{(3)}$ wyliczonym przez algorytm najszybszego spadku jest równy $[-0.18\,\vdots -0.28]$ , a kierunek poprawy wyznaczony w swoim punkcie $x^{(3)}$ przez algorytm gradientu sprzężonego jest równy $[-0.30\,\vdots -0.25]$ . Ta różnica spowodowała, że algorytm gradientu sprzężonego wyznaczył jako punkt $x^{(4)}$ punkt o współrzędnych $(2.25,\,1.10)$ , co dało wartość funkcji celu $f (2.25,\,1.10) = 0.0064$ , a algorytm gradientu prostego – punkt o współrzędnych $(2.37,\,1.16)$ z wartością funkcji celu $f(2.37,\,1.16) = 0.02$ . W piątym kroku algorytm gradientu sprzężonego wyznaczył punkt $x^{(5)} = (2.23,\,1.12)$ dający wartość funkcji celu $f(2.23,\,1.12) = 0.003$ i wartość normy gradientu $||\nabla f(2.23,\,1.12)||=0.05$ , a więc punkt lepszy niż ostatni (ósmy) punkt uzyskany przez algorytm najszybszego spadku (przypominamy był to punkt $(2.27,\,1.12)$ w którym $f (2.27,\,1.12) = 0.0062$ , oraz $||\nabla f(2.27,\,1.12)||=0.09$ .

Rysunek pokazuje kolejne kroki algorytmu gradientu sprzężonego szukającego minimum funkcji Rosenbrocka. Algorytm jest bez odnowy (bo funkcja Rosenbrocka jest dwuwymiarowa) i z minimalizacją w kierunku wykorzystującą wielomian interpolacyjny. Algorytm wykonał 24 iteracje poruszając się po dnie doliny bez zygzakowania i dość szybko w kierunku punktu minimalizującego.

Analiza algorytmu gradientu sprzężonego

Metoda transformacji

"Zerowanie gradientu"

Algorytm Newtona

Transformacja Newtona

Poszukiwanie stosownej transformacji

Oznacza to, że zastosowanie metody stycznych Newtona do rozwiązywania zadania optymalizacji to nic innego jak przyjęcie, że bieżące przybliżenie kwadratowe (84.A) dobrze opisuje zachowanie funkcji minimalizowanej w otoczeniu każdego punktu bieżącego. Zatem z bieżącego punktu należy przejść do punktu w którym funkcja aproksymująca osiąga minimum. W pobliżu lokalnego minimum funkcji celu na pewno takie postępowanie doprowadzi do tego minimum, ale w dużej odległości od niego tak być nie musi, stąd wspomniana wada metody Newtona – gwarantowana zbieżność tylko wtedy gdy algorytm wystartuje w stosownym otoczeniu rozwiązania.

Warunek quasi-newtonowski

Dodatkowe wymagania

Analiza równania (92.A) i wymagania (93,A) pokazała, że poprawka $V^{(k)}$ nie jest określona przez nie jednoznacznie, stąd opracowano wiele wzorów na poprawkę. Z teoretycznego punktu widzenia najciekawsza jest tzw.rodzina poprawek Broydena.

Rodzina poprawek Broydena

Poprawka BFGS

W 1972 r. L.C.W. Dixon pokazał, że z teoretycznego punktu widzenia wszystkie poprawki rodziny Broydena są równoważne – przy dokładnej minimalizacji w kierunku kolejne punkty $x^{(k)}$ obliczone według wzorów (96.A) są przy użyciu dowolnej z nich takie same.