Gradientowe algorytmy rozwiązywania zadań optymalizacji bez ograniczeń



Algorytmy minimalizacji




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.


Metody określania kierunków poprawy




Antygradient kierunkiem poprawy




Jak pamiętamy, przyjęliśmy, że gradient \nabla fjest 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) dox^{(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.


Zbieżność dla funkcji kwadratowych




Algorytmy quasi newtonowskie






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




Pamięć algorytmów







Algorytm quasi-newtonowski BFGS



















Porównanie algorytmu BFGS i gradientu sprzężonego







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


Który algorytm wybrać ?




Oprogramowanie dla zadań liniowych