W tym rozdziale przyjrzymy się wielowymiarowym metodom optymalizacji bez ograniczeń. Zakładamy, że jest funkcją klasy
. 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
, który w naszym przekonaniu znajduje się blisko minimum. W kolejnych krokach generujemy
w ten sposób, aby
. Spodziewamy się, że w ten sposób dojdziemy aż do minimum
. Może się jednak okazać, że punkty skupienia ciągu
nie będą rozwiązaniami. Na kolejnych stronach tego rozdziału zajmiemy się opisem różnych metod konstrukcji ciągu
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
.
Sformułujmy ściśle problem optymalizacyjny:
![]() |
Metodami spadkowymi nazywamy takie algorytmy, w których kolejny punkt zadany jest wzorem
![]() |
gdzie oraz
jest kierunkiem spadku, tzn.
![]() |
![]() |
||
![]() |
![]() |
Zauważmy, że dla dostatecznie małych mamy
(patrz zadanie 13.1). Możemy więc liczyć, że przy dobrym doborze
ciąg punktów
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 jest równoległe do
. 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 .
Krok -ty:
Wybierz krok .
Połóż
Koniec: gdy .
Pozostaje doprecyzowanie reguł znajdowania kroku . Reguły te są stosowane dla dowolnych kierunków spadku
i w takiej formie je prezentujemy. Czytelnik powinien pamiętać, że w przypadku metod największego spadku
.
reguła minimalizacji: wybierz takie że
![]() |
reguła ograniczonej minimalizacji: ustalmy . Wybierz
takie że
![]() |
reguła Armijo: ustalmy i
. Połóżmy
, gdzie
jest najmniejszą liczbą całkowitą nieujemną
spełniającą nierówność
![]() |
Więcej szczegółów podajemy w poniższych podrozdziałach.
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 do
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 Pozostają jednak dwa pytania: czy warunek końca jest poprawny i czy ciąg
zbiega do minimum.
W poniższym twierdzeniu dowodzimy, że każdy punkt skupienia ciągu 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
jest pseudowypukła daje nam pewność, że w znalezionym punkcie jest minimum, które dodatkowo jest globalne.
Niech 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 przeprowadzimy przez sprzeczność. Niech będzie punktem skupienia, zaś
podciągiem do niego zbieżnym. Załóżmy, że
Głównym pomysłem dowodu będzie pokazanie, że istnieje stała
, taka że dla dostatecznie dużych
, tzn. dla
dostatecznie bliskich
, zachodzi
![]() |
czyli możliwe jest zmniejszenie wartości funkcji w kroku
o co najmniej
Pamiętając, że funkcja
maleje wzdłuż ciągu
mamy
![]() |
Przechodząc do granicy z i korzystając z ciągłości
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
jest klasy
) istnieje otoczenie
punktu
, takie że
![]() |
(13.1) |
Głównym spostrzeżeniem pozwalającym na uzasadnienie powyższej nierówności jest to, że na pewnym otoczeniu norma pochodnej
jest ściśle oddzielona od zera.
Weźmy , takie że
oraz dodatkowo w przypadku reguły minimalizacji ograniczonej
(zauważmy, że
na mocy (13.1)). Dla
punkt
należy do
, a więc również do
. Z twierdzenia o wartości średniej dostajemy
![]() |
gdzie jest punktem pośrednim, a więc należy do
. Zajmijmy się teraz produktem pochodnych:
![]() |
![]() |
||
![]() |
|||
![]() |
Wstawiamy to oszacowanie do poprzedniego wzoru:
![]() |
![]() |
||
![]() |
|||
![]() |
gdzie ostatnia nierówność wynika z (13.1). Powyższe oszacowanie jest prawdziwe dla dowolnego a więc dla
dla dostatecznie dużych
. 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 , gdzie
jest punktem początkowym.
Oznaczmy przez
najmniejszą wartość własną macierzy drugich pochodnych
, zaś przez
– jej największą wartość własną.
Załóżmy, że zbiór jest wypukły, funkcja
jest klasy
na otoczeniu
oraz
. Wówczas punkt minimum
należy do
oraz dla dowolnego
![]() |
Dowód lematu 13.1 pozostawiamy jako ćwiczenie. Zauważmy, że założenie o wypukłości jest dość naturalne. Jeśli macierz
jest dodatnio określona, to na pewnej kuli
o środku w
funkcja
jest wypukła. Jeśli
jest jedynym minimum globalnym, to biorąc
dostatecznie bliskie
dostajemy, że zbiór poziomicowy
jest zawarty w kuli
i wnioskujemy dalej, że jest on wypukły.
Załóżmy, że zbiór jest wypukły, funkcja
jest klasy
na otoczeniu
oraz
. Oznaczmy
Wówczas dla ciągu
wygenerowanego przy pomocy metody największego spadku z regułą minimalizacji mamy
![]() |
zaś dla reguły minimalizacji ograniczonej
![]() |
gdzie
![]() |
Rozważmy przypadek reguły minimalizacji bez ograniczeń. Z faktu, że dla każdego
wynika, że
. Na mocy wzoru Taylora, dla
, gdzie
, mamy
![]() |
(13.2) |
Minimum po prawej stronie przyjmowane jest dla Przypomnijmy również, że
realizuje minimum po
z lewej strony. Zatem
![]() |
Odejmijmy od obu stron i zastosujmy nierówność
wynikającą z lematu 13.1:
![]() |
Po prostym przekształceniu dostajemy tezę.
Zajmijmy się regułą minimalizacji ograniczonej. Wówczas realizuje minimum po lewej stronie (13.2) dla
Minimum po prawej stronie przy ograniczeniu
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 jest poprawny i daje ograniczenia zarówno na odległość przybliżenia
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
, tj. czym większe
, tym ostrzejsza zależność między normą gradientu a odległością od punktu
. 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
jest największy, co korzystnie wpływa na współczynnik kontrakcji
. 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
, lub inaczej,
jest tego samego rzędu co
.
Przypomnijmy regułę Armijo. Kładziemy , gdzie
jest najmniejszą liczbą całkowitą nieujemną
spełniającą nierówność
![]() |
Stała 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ż
:
![]() |
(13.3) |
Implementacja metody Armijo jest bardzo łatwa. Startujemy z punktu i sprawdzamy, czy spełniony jest w nim warunek (13.3). Jeśli tak, to kończymy poszukiwanie. W przeciwnym przypadku, rozważamy punkty
W zadaniu 13.3 pokażemy, że w skończonej liczbie kroków znajdziemy punkt spełniający warunek (13.3), jeśli
. Z nierówności (13.3) wynika, że
Niech będzie ciągiem punktów skonstruowanych przez zastosowanie metody najmniejszego spadku z regułą Armijo.
Jeśli istnieje punkt skupienia tego ciągu, to jest on punktem krytycznym.
Jeśli jest punktem krytycznym i macierz
jest dodatnio określona, to istnieje kula
o środku
i promieniu
, taka że gdy
dla pewnego
, to ciąg
dąży do
. W szczególności, jeśli w punkcie skupienia
macierz drugich pochodnych jest dodatnio określona, to cały ciąg zmierza do
.
Dowód pierwszej tezy jest niemal identyczny jak dowód twierdzenia 13.1.
Z faktu, że macierz jest dodatnio określona wynika, że istnieje kula otwarta
o środku
, taka że
jest wypukła w
. Możemy również znaleźć kulę otwartą
o środku w
i mniejszym promieniu niż
, taką że
, jeśli
. Wynika to z ciągłości pochodnej
wokół
i z tego, że się ona w
zeruje. Ciągłość funkcji
pozwala nam wywnioskować, że istnieje zbiór poziomicowy
, dla pewnego
, zawarty w
(zwróć uwagę, że do
wybieramy punkty z większego zbioru
, lecz wymagamy by po zastosowaniu warunktu poziomicowego
było zawarte w
). Zbiór
ma niepuste wnętrze, bo funkcja
jest ciągła i
. Ponadto jest on oddzielony od brzegu
, bo
ma mniejszy promień. Innymi słowy, jeśli odcinek łączy punkt w
z punktem spoza
, to na tym odcinku jest taki punkt
, że
. Wykorzystamy to zaraz. Niech
. Wówczas
(bo
) oraz
. Jeśli teraz
nie zawiera się w
, to, jak ustaliliśmy powyżej, na odcinku łączącym
z
musi istnieć punkt
taki że
. Ale cały ten odcinek leży w
, na którym to zbiorze funkcja
jest wypukła. Nie może więc istnieć na tym odcinku punkt
, w którym wartość jest większa niż w obu jego końcach. Sprzeczność! Wykazaliśmy tym samym, że
. Czyli od pewnego miejsca ciąg
pozostaje w
. Jako, że
jest zwarty, to każdy podciąg
ma w nim punkt skupienia. Z pierwszej częsci twierdzenia wynika, że jest to punkt krytyczny, a takowy może być tylko jeden w
– jest nim
. 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 Nie ma niestety reguł doboru tych parametrów – pozostawia się to doświadczeniu i intuicji użytkownika.
Udowodnij, że jeśli jest kierunkiem spadku w punkcie
, to istnieje
, taka że dla
mamy
![]() |
Udowodnij lemat 13.1.
Przyjrzyj się dokładnie dowodowi lematu 12.4.
Wykaż, że jeśli , to wartość
z reguły Armijo można wyznaczyć w skończonej liczbie kroków (choć różnej dla każdego
).
Rozważ funkcję Zastanów się, dlaczego teza nie jest poprawna dla
.
Zmodyfikuj tezę i dowód lematu 13.2 tak, aby stosował się on do metody Armijo.
Udowodnij, że w metodzie największego spadku z regułą minimalizacji (bez ograniczenia) kolejne kierunki są do siebie prostopadłe.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.