Sformułujmy ściśle problem optymalizacyjny:
Metodami spadkowymi nazywamy takie algorytmy, w których kolejny punkt xk+1 zadany jest wzorem
gdzie αk>0 oraz dk jest kierunkiem spadku, tzn.
| Dfxkdk<0, | jeśli Dfxk≠0, | |
| dk=0, | jeśli Dfxk=0. | |
Zauważmy, że dla dostatecznie małych αk mamy fxk+1<fxk (patrz zadanie 13.1). Możemy więc liczyć, że przy dobrym doborze αk ciąg punktów xk będzie zbiegał do minimum. Niestety nie możemy zagwarantować, że będzie to minimum globalne, ale będziemy starać się znaleźć sposób na zapewnienie zbieżności do minimum lokalnego.
13.1. Reguły minimalizacyjne
Reguła minimalizacji jest dobrze określona, jeśli minimum po prawej stronie istnieje. Do jej implementacji możemy zastosować wówczas metodę Newtona opisaną w poprzednim rozdziale. Ograniczenie przedziału poszukiwań kroku αk do 0,A ma dwie zalety. Po pierwsze zadanie to ma zawsze rozwiązanie, gdyż minimalizujemy funkcję ciągłą na zbiorze zwartym. Po drugie, możemy zastosować szybsze metody poszukiwania minimum podobne do optymalizacji bez użycia pochodnych opisanej w poprzednim rozdziale.
W zadaniu 13.1 dowodzimy, że obie reguły minimalizacyjne wyznaczają krok o tej własności, że fxk+1<fxk. Pozostają jednak dwa pytania: czy warunek końca jest poprawny i czy ciąg xk zbiega do minimum.
W poniższym twierdzeniu dowodzimy, że każdy punkt skupienia ciągu xk jest punktem krytycznym, tzn. zeruje się w nim pochodna. Nie jest jednak w ogólności prawdą, że musi w nim być minimum lokalne. Dopiero założenie, że funkcja f jest pseudowypukła daje nam pewność, że w znalezionym punkcie jest minimum, które dodatkowo jest globalne.
Twierdzenie 13.1
Niech xk będzie ciągiem skonstruowanym przy pomocy metody największego spadku z regułą minimalizacji lub minimalizacji ograniczonej. Wówczas każdy punkt skupienia tego ciągu jest punktem krytycznym.
Dowód
Dowód przeprowadzimy przez sprzeczność. Niech x¯ będzie punktem skupienia, zaś xkn podciągiem do niego zbieżnym. Załóżmy, że Dfx¯≠0T. Głównym pomysłem dowodu będzie pokazanie, że istnieje stała γ>0, taka że dla dostatecznie dużych n, tzn. dla xkn dostatecznie bliskich x¯, zachodzi
czyli możliwe jest zmniejszenie wartości funkcji f w kroku kn o co najmniej γ. Pamiętając, że funkcja f maleje wzdłuż ciągu xk mamy
Przechodząc do granicy z n→∞ i korzystając z ciągłości f dostajemy sprzeczność z dodatniością γ.
Do zakończenia dowodu pozostaje nam udowodnienie istnienia takiej stałej γ. Na mocy ciągłości pochodnej (przypomnijmy, że w tym rozdziale zakładamy, że f jest klasy C1) istnieje otoczenie V punktu x¯, takie że
| Dfx-DfyDfx≤12,∀x,y∈V. | | (13.1) |
Głównym spostrzeżeniem pozwalającym na uzasadnienie powyższej nierówności jest to, że na pewnym otoczeniu x¯ norma pochodnej f jest ściśle oddzielona od zera.
Weźmy δ>0, takie że Bx¯,2δ⊂V oraz dodatkowo w przypadku reguły minimalizacji ograniczonej δ≤Ainfx∈VDfx (zauważmy, że infx∈VDfx>0 na mocy (13.1)). Dla x∈Bx¯,δ punkt x-δDfxT/Dfx należy do Bx,2δ, a więc również do V. Z twierdzenia o wartości średniej dostajemy
| fx-fx-δDfxTDfx=DfθδDfxTDfx=δDfxDfθDfxT, | |
gdzie θ jest punktem pośrednim, a więc należy do V. Zajmijmy się teraz produktem pochodnych:
| DfθDfxT | =Dfx+Dfθ-DfxDfxT | |
| | =Dfx2+Dfθ-DfxDfxT | |
| | ≥Dfx2-Dfθ-DfxDfx. | |
Wstawiamy to oszacowanie do poprzedniego wzoru:
| fx-fx-δDfxTDfx | ≥δDfx-δDfθ-Dfx | |
| | =δDfx1-Dfθ-DfxDfx | |
| | ≥δ2Dfx, | |
gdzie ostatnia nierówność wynika z (13.1). Powyższe oszacowanie jest prawdziwe dla dowolnego x∈Bx¯,δ, a więc dla xkn dla dostatecznie dużych n. Możemy zatem przyjąć
∎
Powyższe twierdzenie dowodzi poprawności metody największego spadku, lecz nie mówi nic o szybkości zbieżności i o warunku końca. Wzmacniając założenia będziemy mogli dowieść, że zbieżność jest wykładniczo szybka oraz, podobnie jak w lemacie 12.4, warunek końca jest poprawny.
Zdefiniujmy zbiór S=x∈Rn:fx≤fx0, gdzie x0 jest punktem początkowym.
Oznaczmy przez mx najmniejszą wartość własną macierzy drugich pochodnych D2fx, zaś przez Mx – jej największą wartość własną.
Lemat 13.1
Załóżmy, że zbiór S jest wypukły, funkcja f jest klasy C2 na otoczeniu S oraz m=infx∈Smx>0. Wówczas punkt minimum x¯ należy do S oraz dla dowolnego x∈S
| x-x¯≤1mDfx,fx-fx¯≤1mDfx2. | |
Dowód lematu 13.1 pozostawiamy jako ćwiczenie. Zauważmy, że założenie o wypukłości S jest dość naturalne. Jeśli macierz D2fx¯ jest dodatnio określona, to na pewnej kuli B o środku w x¯ funkcja f jest wypukła. Jeśli x¯ jest jedynym minimum globalnym, to biorąc x0 dostatecznie bliskie x¯ dostajemy, że zbiór poziomicowy S jest zawarty w kuli B i wnioskujemy dalej, że jest on wypukły.
Lemat 13.2
Załóżmy, że zbiór S jest wypukły, funkcja f jest klasy C2 na otoczeniu S oraz m=infx∈Smx>0. Oznaczmy M=supx∈SMx. Wówczas dla ciągu xk wygenerowanego przy pomocy metody największego spadku z regułą minimalizacji mamy
| fxk+1-fx¯≤1-m2Mfxk-fx¯, | |
zaś dla reguły minimalizacji ograniczonej
| fxk+1-fx¯≤1-mγ+mMγ22fxk-fx¯, | |
gdzie
Dowód
Rozważmy przypadek reguły minimalizacji bez ograniczeń. Z faktu, że fxk+1≤fxk dla każdego k wynika, że xk⊂S. Na mocy wzoru Taylora, dla α∈0,α¯, gdzie α¯=supα≥0:xk-αDfxkT∈S, mamy
| fxk-αDfxkT≤fxk+Dfxk-αDfxkT+α2M2Dfxk2=fxk-αDfxk2+α2M2Dfxk2. | | (13.2) |
Minimum po prawej stronie przyjmowane jest dla α=1/M. Przypomnijmy również, że xk+1 realizuje minimum po α≥0 z lewej strony. Zatem
| fxk+1≤fxk-12MDfxk2. | |
Odejmijmy od obu stron fx¯ i zastosujmy nierówność Dfxk2≥mfxk-fx¯ wynikającą z lematu 13.1:
| fxk+1-fx¯≤fxk-fx¯-m2Mfxk-fx¯. | |
Po prostym przekształceniu dostajemy tezę.
Zajmijmy się regułą minimalizacji ograniczonej. Wówczas xk+1 realizuje minimum po lewej stronie (13.2) dla α∈[0,A∥). Minimum po prawej stronie przy ograniczeniu α≤minA,α¯ realizowane jest przez α=γ, patrz rys. 13.1. Postępując teraz identycznie jak powyżej dostajemy tezę.
∎
Podsumujmy. Na mocy lematu 13.1 wiemy, że warunek końca sformułowany jako ograniczenie na normę gradientu funkcji f jest poprawny i daje ograniczenia zarówno na odległość przybliżenia xk+1 od punktu minimum, jak i na dokładność wyznaczenia wartości minimalnej funkcji. Zwróćmy uwagę, że czym ”bardziej” ściśle wypukła jest funkcja na otoczeniu x¯, tj. czym większe m, tym ostrzejsza zależność między normą gradientu a odległością od punktu x¯. Lemat 13.2 sugeruje, że zbieżność wartości funkcji jest najszybsza, jeśli funkcja podobnie zachowuje się we wszystkich kierunkach, czyli wartości własne macierzy drugich pochodnych leżą dość blisko siebie. Wówczas iloraz m/M jest największy, co korzystnie wpływa na współczynnik kontrakcji 1-m/2M. A zatem algorytm największego spadku, podobnie jak wszystkie inne metody spadkowe, będzie najlepiej pracował na takich funkcjach, które mają stosunkowo duży iloraz m/M, lub inaczej, m jest tego samego rzędu co M.
13.2. Reguła Armijo
Przypomnijmy regułę Armijo. Kładziemy αk=βmks, gdzie mk jest najmniejszą liczbą całkowitą nieujemną m spełniającą nierówność
| fxk-fxk+βmsdk≥-σβmsDfxkdk. | |
Stała s>0 nazywana jest krokiem, β reguluje szybkość zmniejszania kroku (czym mniejsza wartość, tym szybciej krok się zmniejsza), zaś σ odpowiedzialna jest za ostrość warunku: mniejsza wartość osłabia warunek. Zauważmy, że w przypadku metody największego spadku warunek powyższy upraszcza się nieznacznie, ponieważ Dfxkdk=-Dfxk2:
| fxk-fxk-βmsDfxkT≥σβmsDfxk2. | | (13.3) |
Implementacja metody Armijo jest bardzo łatwa. Startujemy z punktu xk-sDfxkT i sprawdzamy, czy spełniony jest w nim warunek (13.3). Jeśli tak, to kończymy poszukiwanie. W przeciwnym przypadku, rozważamy punkty xk-βsDfxkT,xk-β2sDfxkT,….
W zadaniu 13.3 pokażemy, że w skończonej liczbie kroków znajdziemy punkt spełniający warunek (13.3), jeśli dk≠0. Z nierówności (13.3) wynika, że fxk+1<fxk.
Twierdzenie 13.2
Niech xk będzie ciągiem punktów skonstruowanych przez zastosowanie metody najmniejszego spadku z regułą Armijo.
-
Jeśli istnieje punkt skupienia x¯ tego ciągu, to jest on punktem krytycznym.
-
Jeśli x¯ jest punktem krytycznym i macierz D2fx¯ jest dodatnio określona, to istnieje kula Bx¯,ε o środku x¯ i promieniu ε>0, taka że gdy xk∈Bx¯,ε dla pewnego k, to ciąg xk dąży do x¯. W szczególności, jeśli w punkcie skupienia x¯ macierz drugich pochodnych jest dodatnio określona, to cały ciąg zmierza do x¯.
Dowód
Dowód pierwszej tezy jest niemal identyczny jak dowód twierdzenia 13.1.
Z faktu, że macierz D2fx¯ jest dodatnio określona wynika, że istnieje kula otwarta B1 o środku x¯, taka że f jest wypukła w B1. Możemy również znaleźć kulę otwartą B2 o środku w x¯ i mniejszym promieniu niż B1, taką że x-sDfxT∈B1, jeśli x∈B2. Wynika to z ciągłości pochodnej Df wokół x¯ i z tego, że się ona w x¯ zeruje. Ciągłość funkcji f pozwala nam wywnioskować, że istnieje zbiór poziomicowy S=x∈B1:fx≤α, dla pewnego α>fx¯, zawarty w B2 (zwróć uwagę, że do S wybieramy punkty z większego zbioru B1, lecz wymagamy by po zastosowaniu warunktu poziomicowego S było zawarte w B2). Zbiór S ma niepuste wnętrze, bo funkcja f jest ciągła i α>fx¯. Ponadto jest on oddzielony od brzegu B1, bo B2 ma mniejszy promień. Innymi słowy, jeśli odcinek łączy punkt w S z punktem spoza S, to na tym odcinku jest taki punkt y, że fy>α. Wykorzystamy to zaraz. Niech xk∈S. Wówczas xk+1∈B1 (bo S⊂B2) oraz fxk+1<fxk. Jeśli teraz xk+1 nie zawiera się w S, to, jak ustaliliśmy powyżej, na odcinku łączącym xk z xk+1 musi istnieć punkt y, taki że fy>α≥fxk>fxk+1. Ale cały ten odcinek leży w B1, na którym to zbiorze funkcja f jest wypukła. Nie może więc istnieć na tym odcinku punkt y, w którym wartość jest większa niż w obu jego końcach. Sprzeczność! Wykazaliśmy tym samym, że xk+1∈S. Czyli od pewnego miejsca ciąg xk pozostaje w S. Jako, że S jest zwarty, to każdy podciąg xk ma w nim punkt skupienia. Z pierwszej częsci twierdzenia wynika, że jest to punkt krytyczny, a takowy może być tylko jeden w B1 – jest nim x¯. Udowodniliśmy więc drugą część twierdzenia.
∎
Poprawność warunku stopu algorytmu pozostaje w mocy, gdyż Lemat 13.1 nie zależy od metody optymalizacyjnej. Teza lematu 13.2 wymaga pewnych zmian, pozostawiając jednak wykładniczą zbieżność (patrz zadanie 13.4).
Jakie zatem są zalety reguły Armijo? Otóż, jak wspomniane zostało wyżej, jest ona prosta w implementacji i nie wymaga stosowania metod optymalizacji funkcji jednej zmiennej. Koszt tego uproszczenia nie jest zwykle również duży, lecz zależy od parametrów s,β,σ. Nie ma niestety reguł doboru tych parametrów – pozostawia się to doświadczeniu i intuicji użytkownika.
