MO Moduł 7

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
MO M7 Slajd1.png

MO M7 Slajd2.png
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

MO M7 Slajd3.png

MO M7 Slajd4.png
Jak pamiętamy, przyjęliśmy, że gradient jest wektorem wierszowym. Jego transpozycję do wektora kolumnowego oznacza się .

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

MO M7 Slajd6.png

MO M7 Slajd7.png

MO M7 Slajd8.png

MO M7 Slajd9.png

MO M7 Slajd10.png

MO M7 Slajd11.png

MO M7 Slajd12.png

MO M7 Slajd13.png

MO M7 Slajd14.png
Algorytm wykonał osiem kroków i zatrzymał się w punkcie w którym . Wartość funkcji celu , a odległość
.

MO M7 Slajd15.png

MO M7 Slajd16.png

MO M7 Slajd17.png
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 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.

MO M7 Slajd18.png

MO M7 Slajd19.png

MO M7 Slajd20.png
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.

MO M7 Slajd21.png

MO M7 Slajd22.png

MO M7 Slajd23.png
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 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".

MO M7 Slajd24.png

MO M7 Slajd25.png

MO M7 Slajd26.png

MO M7 Slajd27.png

MO M7 Slajd28.png

MO M7 Slajd29.png

MO M7 Slajd30.png

MO M7 Slajd31.png

MO M7 Slajd32.png

MO M7 Slajd33.png

MO M7 Slajd34.png

MO M7 Slajd35.png

MO M7 Slajd36.png

MO M7 Slajd37.png

MO M7 Slajd38.png

MO M7 Slajd39.png

MO M7 Slajd40.png

MO M7 Slajd41.png
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ść.



MO M7 Slajd42.png

MO M7 Slajd43.png

MO M7 Slajd44.png

MO M7 Slajd45.png

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

MO M7 Slajd47.png

MO M7 Slajd48.png

MO M7 Slajd49.png

MO M7 Slajd50.png

MO M7 Slajd51.png

MO M7 Slajd52.png

MO M7 Slajd53.png

MO M7 Slajd54.png

MO M7 Slajd55.png

MO M7 Slajd56.png

MO M7 Slajd57.png

MO M7 Slajd58.png

MO M7 Slajd59.png

MO M7 Slajd60.png

MO M7 Slajd61.png

MO M7 Slajd62.png

MO M7 Slajd63.png

MO M7 Slajd64.png

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

MO M7 Slajd66.png

MO M7 Slajd67.png

MO M7 Slajd68.png

MO M7 Slajd69.png

MO M7 Slajd70.png
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.

MO M7 Slajd71.png

MO M7 Slajd72.png
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 i miał znaleźć rozwiązanie z dokładnością (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 w którym . Wartość funkcji celu , a odległość proponowanego rozwiązania od punktu optymalnego jest równa
.

Krok pierwszy z do 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ż . Zadanie jest dwuwymiarowe, zatem odnowa (ruch w kierunku antygradientu) nastąpiła w kroku trzecim, piątym i ostatnim – siódmym. Ponieważ punkty 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 , które też będą leżały blisko siebie. Lecz antygradient policzony w punkcie wyliczonym przez algorytm najszybszego spadku jest równy , a kierunek poprawy wyznaczony w swoim punkcie przez algorytm gradientu sprzężonego jest równy . Ta różnica spowodowała, że algorytm gradientu sprzężonego wyznaczył jako punkt punkt o współrzędnych , co dało wartość funkcji celu , a algorytm gradientu prostego – punkt o współrzędnych z wartością funkcji celu . W piątym kroku algorytm gradientu sprzężonego wyznaczył punkt dający wartość funkcji celu i wartość normy gradientu , a więc punkt lepszy niż ostatni (ósmy) punkt uzyskany przez algorytm najszybszego spadku (przypominamy był to punkt w którym , oraz .


MO M7 Slajd73.png
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

MO M7 Slajd74.png

MO M7 Slajd75.png

MO M7 Slajd76.png

MO M7 Slajd77.png

MO M7 Slajd78.png

MO M7 Slajd79.png

MO M7 Slajd80.png

MO M7 Slajd81.png

MO M7 Slajd82.png

MO M7 Slajd83.png

MO M7 Slajd84.png

MO M7 Slajd85.png

MO M7 Slajd86.png

MO M7 Slajd87.png
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

MO M7 Slajd88.png

MO M7 Slajd89.png

MO M7 Slajd90.png

MO M7 Slajd91.png

MO M7 Slajd92.png

MO M7 Slajd93.png
Analiza równania (92.A) i wymagania (93,A) pokazała, że poprawka 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.

MO M7 Slajd94.png

MO M7 Slajd95.png

MO M7 Slajd96.png

MO M7 Slajd97.png
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 obliczone według wzorów (96.A) są przy użyciu dowolnej z nich takie same.

MO M7 Slajd98.png

MO M7 Slajd99.png

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

MO M7 Slajd101.png

MO M7 Slajd102.png

MO M7 Slajd103.png

MO M7 Slajd104.png

MO M7 Slajd105.png

MO M7 Slajd106.png

MO M7 Slajd107.png

MO M7 Slajd108.png

MO M7 Slajd109.png

MO M7 Slajd110.png

MO M7 Slajd111.png

MO M7 Slajd112.png

MO M7 Slajd113.png

MO M7 Slajd114.png

MO M7 Slajd115.png

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

MO M7 Slajd117.png

MO M7 Slajd118.png