MO Moduł 7

---

Jak się o tym zaraz przekonamy rozważania teoretyczne (i wzory) potrzebne do zrozumienia zasad działania metod kierunków poprawy nie są łatwe. Dla metod obszaru zaufania są nieco bardziej skomplikowane i dlatego omawiać ich nie będziemy

---

---

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

---

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

---

---

---

---

---

---

---

---

---

Algorytm wykonał osiem kroków i zatrzymał się w punkcie $x^{(8)}=(2.27,1.12)$ w którym $||\mathrm{\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$.

---

---

---

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.

---

---

---

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.

---

---

---

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".

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

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.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

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.

---

---

---

---

---

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ą $\epsilon =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 $||\mathrm{\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⋮-0.28]$, a kierunek poprawy wyznaczony w swoim punkcie $x^{(3)}$ przez algorytm gradientu sprzężonego jest równy $[-0.30⋮-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 $||\mathrm{\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 $||\mathrm{\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

---

---

---

---

---

---

---

---

---

---

---

---

---

---

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

---

---

---

---

---

---

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.

---

---

---

---

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.

---

---

---

Twierdzenie (7.2QN) wskazuje na związek miedzy algorytmami quasi-newtonowskimi i algorytmami gradientu sprzężonego. Można też wskazać i różnice.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

Algorytm gradientu sprzężonego zużył 24 iteracje na dotarcie do rozwiązania, a quasi-newtonowskiemu algorytmowi BFGS wystarczyło tylko 11 iteracji.

---

---

---