Zagadnienia

13. Metody spadkowe

W tym rozdziale przyjrzymy się wielowymiarowym metodom optymalizacji bez ograniczeń. Zakładamy, że f:RnR jest funkcją klasy C1. Naszym celem jest znalezienie jej minimum. Wszystkie opisywane metody zbudowane są w oparciu o następujący ogólny schemat. Startujemy z punktu początkowego x0, który w naszym przekonaniu znajduje się blisko minimum. W kolejnych krokach generujemy x1,x2, w ten sposób, aby fxk+1<fxk. Spodziewamy się, że w ten sposób dojdziemy aż do minimum f. Może się jednak okazać, że punkty skupienia ciągu xk nie będą rozwiązaniami. Na kolejnych stronach tego rozdziału zajmiemy się opisem różnych metod konstrukcji ciągu xk i ich zbieżnością do rozwiązania. Wszystkie wyniki tego rozdziału w oczywisty sposób przenoszą się na przypadek funkcji określonych na zbiorach otwartych w Rn.

Sformułujmy ściśle problem optymalizacyjny:

fxmin,xRn.

Metodami spadkowymi nazywamy takie algorytmy, w których kolejny punkt xk+1 zadany jest wzorem

xk+1=xk+αkdk,

gdzie αk>0 oraz dk jest kierunkiem spadku, tzn.

Dfxkdk<0,jeśli Dfxk0,
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.

W tym rozdziale skupimy się na metodach największego spadku, czyli takich że dk jest równoległe do DfxkT. Metody spadkowe będą również grały pierwsze skrzypce w następnym rozdziale, przy optymalizacji numerycznej z ograniczeniami.

Algorytm opisujący metody największego spadku jest dość prosty:

  • Inicjalizacja: Wybierz punkt początkowy x0.

  • Krok k-ty:

    1. Wybierz krok αk.

    2. Połóż xk+1=xk-αkDfxkT.

  • Koniec: gdy Dfxk+1ε.

Pozostaje doprecyzowanie reguł znajdowania kroku αk. Reguły te są stosowane dla dowolnych kierunków spadku dk i w takiej formie je prezentujemy. Czytelnik powinien pamiętać, że w przypadku metod największego spadku dk=-DfxkT.

  • reguła minimalizacji: wybierz αk takie że

    fxk+αkdk=minα0fxk+αdk.
  • reguła ograniczonej minimalizacji: ustalmy A>0. Wybierz αk takie że

    fxk+αkdk=minα0,Afxk+αdk.
  • reguła Armijo: ustalmy s>0 i β,σ0,1. Połóżmy αk=βmks, gdzie mk jest najmniejszą liczbą całkowitą nieujemną m spełniającą nierówność

    fxk-fxk+βmsdk-σβmsDfxkdk.

Więcej szczegółów podajemy w poniższych podrozdziałach.

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

fxkn+1fxkn-γ,

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

fxkn+1fxkn+1fxkn-γ.

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-DfyDfx12,x,yV.(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 δAinfxVDfx (zauważmy, że infxVDfx>0 na mocy (13.1)). Dla xBx¯,δ 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 xBx¯,δ, a więc dla xkn dla dostatecznie dużych n. Możemy zatem przyjąć

γ=δ2infxBx¯,δDfx.

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=xRn:fxfx0, 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=infxSmx>0. Wówczas punkt minimum x¯ należy do S oraz dla dowolnego xS

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=infxSmx>0. Oznaczmy M=supxSMx. 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

γ=min1M,A.
Dowód

Rozważmy przypadek reguły minimalizacji bez ograniczeń. Z faktu, że fxk+1fxk dla każdego k wynika, że xkS. Na mocy wzoru Taylora, dla α0,α¯, gdzie α¯=supα0:xk-αDfxkTS, mamy

fxk-αDfxkTfxk+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+1fxk-12MDfxk2.

Odejmijmy od obu stron fx¯ i zastosujmy nierówność Dfxk2mfxk-fx¯ wynikającą z lematu 13.1:

fxk+1-fx¯fxk-fx¯-m2Mfxk-fx¯.

Po prostym przekształceniu dostajemy tezę.

Rys. 13.1. Wykres funkcji αM2α2-α.

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

  1. Jeśli istnieje punkt skupienia x¯ tego ciągu, to jest on punktem krytycznym.

  2. 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 xkBx¯,ε 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-sDfxTB1, jeśli xB2. 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=xB1: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 xkS. Wówczas xk+1B1 (bo SB2) 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+1S. 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.

13.3. Zadania

Ćwiczenie 13.1

Udowodnij, że jeśli d jest kierunkiem spadku w punkcie x, to istnieje δ>0, taka że dla α0,δ mamy

fx+αd<fx.
Ćwiczenie 13.2

Udowodnij lemat 13.1.

Wskazówka: 

Przyjrzyj się dokładnie dowodowi lematu 12.4.

Ćwiczenie 13.3

Wykaż, że jeśli dk0, to wartość αk z reguły Armijo można wyznaczyć w skończonej liczbie kroków (choć różnej dla każdego xk).

Wskazówka: 

Rozważ funkcję gα=fx-fx-αDfxT-σαDfx2. Zastanów się, dlaczego teza nie jest poprawna dla σ1.

Ćwiczenie 13.4

Zmodyfikuj tezę i dowód lematu 13.2 tak, aby stosował się on do metody Armijo.

Ćwiczenie 13.5

Udowodnij, że w metodzie największego spadku z regułą minimalizacji (bez ograniczenia) kolejne kierunki dk są do siebie prostopadłe.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.