Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja II – 13. Metody spadkowe – MIM UW

Zagadnienia

13. Metody spadkowe

W tym rozdziale przyjrzymy się wielowymiarowym metodom optymalizacji bez ograniczeń. Zakładamy, że f:\mathbb{R}^{n}\to\mathbb{R} jest funkcją klasy C^{1}. 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 \mathbf{x}_{0}, który w naszym przekonaniu znajduje się blisko minimum. W kolejnych krokach generujemy \mathbf{x}_{1},\mathbf{x}_{2},\ldots w ten sposób, aby f(\mathbf{x}_{{k+1}})<f(\mathbf{x}_{k}). Spodziewamy się, że w ten sposób dojdziemy aż do minimum f. Może się jednak okazać, że punkty skupienia ciągu (\mathbf{x}_{k}) nie będą rozwiązaniami. Na kolejnych stronach tego rozdziału zajmiemy się opisem różnych metod konstrukcji ciągu (\mathbf{x}_{k}) 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 \mathbb{R}^{n}.

Sformułujmy ściśle problem optymalizacyjny:

\begin{cases}f(\mathbf{x})\to\min,&\\
\mathbf{x}\in\mathbb{R}^{n}.&\end{cases}

Metodami spadkowymi nazywamy takie algorytmy, w których kolejny punkt \mathbf{x}_{{k+1}} zadany jest wzorem

\mathbf{x}_{{k+1}}=\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k},

gdzie \alpha _{k}>0 oraz \mathbf{d}_{k} jest kierunkiem spadku, tzn.

\displaystyle Df(\mathbf{x}_{k})\mathbf{d}_{k}<0, \displaystyle\quad\text{jeśli }Df(\mathbf{x}_{k})\ne\mathbf{0},
\displaystyle\mathbf{d}_{k}=0, \displaystyle\quad\text{jeśli }Df(\mathbf{x}_{k})=\mathbf{0}.

Zauważmy, że dla dostatecznie małych \alpha _{k} mamy f(\mathbf{x}_{{k+1}})<f(\mathbf{x}_{k}) (patrz zadanie 13.1). Możemy więc liczyć, że przy dobrym doborze \alpha _{k} ciąg punktów (\mathbf{x}_{k}) 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 \mathbf{d}_{k} jest równoległe do \big(Df(\mathbf{x}_{k})\big)^{T}. 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 \mathbf{x}_{0}.

  • Krok k-ty:

    1. Wybierz krok \alpha _{k}.

    2. Połóż \displaystyle x_{{k+1}}=\mathbf{x}_{k}-\alpha _{k}\big(Df(\mathbf{x}_{k})\big)^{T}.

  • Koniec: gdy \| Df(x_{{k+1}})\|\le\varepsilon.

Pozostaje doprecyzowanie reguł znajdowania kroku \alpha _{k}. Reguły te są stosowane dla dowolnych kierunków spadku \mathbf{d}_{k} i w takiej formie je prezentujemy. Czytelnik powinien pamiętać, że w przypadku metod największego spadku \mathbf{d}_{k}=-\big(Df(\mathbf{x}_{k})\big)^{T}.

  • reguła minimalizacji: wybierz \alpha _{k} takie że

    f(\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k})=\min _{{\alpha\ge 0}}f(\mathbf{x}_{k}+\alpha\mathbf{d}_{k}).
  • reguła ograniczonej minimalizacji: ustalmy A>0. Wybierz \alpha _{k} takie że

    f(\mathbf{x}_{k}+\alpha _{k}\mathbf{d}_{k})=\min _{{\alpha\in[0,A]}}f(\mathbf{x}_{k}+\alpha\mathbf{d}_{k}).
  • reguła Armijo: ustalmy s>0 i \beta,\sigma\in(0,1). Połóżmy \alpha _{k}=\beta^{{m_{k}}}s, gdzie m_{k} jest najmniejszą liczbą całkowitą nieujemną m spełniającą nierówność

    f(\mathbf{x}_{k})-f(\mathbf{x}_{k}+\beta^{m}s\,\mathbf{d}_{k})\ge-\sigma\beta^{m}s\; Df(\mathbf{x}_{k})\mathbf{d}_{k}.

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 \alpha _{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 f(\mathbf{x}_{{k+1}})<f(\mathbf{x}_{k}). Pozostają jednak dwa pytania: czy warunek końca jest poprawny i czy ciąg (\mathbf{x}_{k}) zbiega do minimum.

W poniższym twierdzeniu dowodzimy, że każdy punkt skupienia ciągu (\mathbf{x}_{k}) 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 (\mathbf{x}_{k}) 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 {\bar{\mathbf{x}}} będzie punktem skupienia, zaś (\mathbf{x}_{{k_{n}}}) podciągiem do niego zbieżnym. Załóżmy, że Df({\bar{\mathbf{x}}})\ne\mathbf{0}^{T}. Głównym pomysłem dowodu będzie pokazanie, że istnieje stała \gamma>0, taka że dla dostatecznie dużych n, tzn. dla \mathbf{x}_{{k_{n}}} dostatecznie bliskich {\bar{\mathbf{x}}}, zachodzi

f(\mathbf{x}_{{k_{n}+1}})\le f(\mathbf{x}_{{k_{n}}})-\gamma,

czyli możliwe jest zmniejszenie wartości funkcji f w kroku k_{n} o co najmniej \gamma. Pamiętając, że funkcja f maleje wzdłuż ciągu (\mathbf{x}_{k}) mamy

f(\mathbf{x}_{{k_{{n+1}}}})\le f(\mathbf{x}_{{k_{n}+1}})\le f(\mathbf{x}_{{k_{n}}})-\gamma.

Przechodząc do granicy z n\to\infty i korzystając z ciągłości f dostajemy sprzeczność z dodatniością \gamma.

Do zakończenia dowodu pozostaje nam udowodnienie istnienia takiej stałej \gamma. Na mocy ciągłości pochodnej (przypomnijmy, że w tym rozdziale zakładamy, że f jest klasy C^{1}) istnieje otoczenie V punktu {\bar{\mathbf{x}}}, takie że

\frac{\| Df(\mathbf{x})-Df(\mathbf{y})\|}{\| Df(\mathbf{x})\|}\le\frac{1}{2},\qquad\forall\ \mathbf{x},\mathbf{y}\in V. (13.1)

Głównym spostrzeżeniem pozwalającym na uzasadnienie powyższej nierówności jest to, że na pewnym otoczeniu {\bar{\mathbf{x}}} norma pochodnej f jest ściśle oddzielona od zera.

Weźmy \delta>0, takie że B({\bar{\mathbf{x}}},2\delta)\subset V oraz dodatkowo w przypadku reguły minimalizacji ograniczonej \delta\le A\inf _{{\mathbf{x}\in V}}\| Df(\mathbf{x})\| (zauważmy, że \inf _{{\mathbf{x}\in V}}\| Df(\mathbf{x})\|>0 na mocy (13.1)). Dla \mathbf{x}\in B({\bar{\mathbf{x}}},\delta) punkt \mathbf{x}-\delta\big(Df(\mathbf{x})\big)^{T}/\| Df(\mathbf{x})\| należy do B(\mathbf{x},2\delta), a więc również do V. Z twierdzenia o wartości średniej dostajemy

f(\mathbf{x})-f\bigg(\mathbf{x}-\delta\frac{\big(Df(\mathbf{x})\big)^{T}}{\| Df(\mathbf{x})\|}\bigg)=Df(\theta)\bigg(\delta\frac{\big(Df(\mathbf{x})\big)^{T}}{\| Df(\mathbf{x})\|}\bigg)=\frac{\delta}{\| Df(\mathbf{x})\|}Df(\theta)\big(Df(\mathbf{x})\big)^{T},

gdzie \theta jest punktem pośrednim, a więc należy do V. Zajmijmy się teraz produktem pochodnych:

\displaystyle Df(\theta)\big(Df(\mathbf{x})\big)^{T} \displaystyle=\Big(Df(\mathbf{x})+Df(\theta)-Df(\mathbf{x})\Big)\big(Df(\mathbf{x})\big)^{T}
\displaystyle=\| Df(\mathbf{x})\|^{2}+\big(Df(\theta)-Df(\mathbf{x})\big)\big(Df(\mathbf{x})\big)^{T}
\displaystyle\ge\| Df(\mathbf{x})\|^{2}-\| Df(\theta)-Df(\mathbf{x})\|\| Df(\mathbf{x})\|.

Wstawiamy to oszacowanie do poprzedniego wzoru:

\displaystyle f(\mathbf{x})-f\bigg(\mathbf{x}-\delta\frac{\big(Df(\mathbf{x})\big)^{T}}{\| Df(\mathbf{x})\|}\bigg) \displaystyle\ge\delta\| Df(\mathbf{x})\|-\delta\| Df(\theta)-Df(\mathbf{x})\|
\displaystyle=\delta\| Df(\mathbf{x})\|\bigg(1-\frac{\| Df(\theta)-Df(\mathbf{x})\|}{\| Df(\mathbf{x})\|}\bigg)
\displaystyle\ge\frac{\delta}{2}\| Df(\mathbf{x})\|,

gdzie ostatnia nierówność wynika z (13.1). Powyższe oszacowanie jest prawdziwe dla dowolnego \mathbf{x}\in B({\bar{\mathbf{x}}},\delta), a więc dla \mathbf{x}_{{k_{n}}} dla dostatecznie dużych n. Możemy zatem przyjąć

\gamma=\frac{\delta}{2}\inf _{{\mathbf{x}\in B({\bar{\mathbf{x}}},\delta)}}\| Df(\mathbf{x})\|.

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=\{\mathbf{x}\in\mathbb{R}^{n}:\  f(\mathbf{x})\le f(\mathbf{x}_{0})\}, gdzie \mathbf{x}_{0} jest punktem początkowym. Oznaczmy przez m(\mathbf{x}) najmniejszą wartość własną macierzy drugich pochodnych D^{2}f(\mathbf{x}), zaś przez M(\mathbf{x}) – jej największą wartość własną.

Lemat 13.1

Załóżmy, że zbiór S jest wypukły, funkcja f jest klasy C^{2} na otoczeniu S oraz m=\inf _{{\mathbf{x}\in S}}m(\mathbf{x})>0. Wówczas punkt minimum {\bar{\mathbf{x}}} należy do S oraz dla dowolnego \mathbf{x}\in S

\|\mathbf{x}-{\bar{\mathbf{x}}}\|\le\frac{1}{m}\| Df(\mathbf{x})\|,\qquad f(\mathbf{x})-f({\bar{\mathbf{x}}})\le\frac{1}{m}\| Df(\mathbf{x})\|^{2}.

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 D^{2}f({\bar{\mathbf{x}}}) jest dodatnio określona, to na pewnej kuli B o środku w {\bar{\mathbf{x}}} funkcja f jest wypukła. Jeśli {\bar{\mathbf{x}}} jest jedynym minimum globalnym, to biorąc \mathbf{x}_{0} dostatecznie bliskie {\bar{\mathbf{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 C^{2} na otoczeniu S oraz m=\inf _{{\mathbf{x}\in S}}m(\mathbf{x})>0. Oznaczmy M=\sup _{{\mathbf{x}\in S}}M(\mathbf{x}). Wówczas dla ciągu (\mathbf{x}_{k}) wygenerowanego przy pomocy metody największego spadku z regułą minimalizacji mamy

f(\mathbf{x}_{{k+1}})-f({\bar{\mathbf{x}}})\le\Big(1-\frac{m}{2M}\Big)\big(f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})\big),

zaś dla reguły minimalizacji ograniczonej

f(\mathbf{x}_{{k+1}})-f({\bar{\mathbf{x}}})\le\Big(1-m\gamma+\frac{mM\gamma^{2}}{2}\Big)\big(f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})\big),

gdzie

\gamma=\min\Big(\frac{1}{M},A\Big).
Dowód

Rozważmy przypadek reguły minimalizacji bez ograniczeń. Z faktu, że f(\mathbf{x}_{{k+1}})\le f(\mathbf{x}_{k}) dla każdego k wynika, że (\mathbf{x}_{k})\subset S. Na mocy wzoru Taylora, dla \alpha\in[0,\bar{\alpha}], gdzie \bar{\alpha}=\sup\{\alpha\ge 0:\ \mathbf{x}_{k}-\alpha\big(Df(\mathbf{x}_{k})\big)^{T}\in S\}, mamy

\begin{aligned}\displaystyle f\big(\mathbf{x}_{k}-\alpha\big(Df(\mathbf{x}_{k})\big)^{T}\big)&\displaystyle\le f(\mathbf{x}_{k})+Df(\mathbf{x}_{k})\big(-\alpha(Df(\mathbf{x}_{k}))^{T}\big)+\alpha^{2}\frac{M}{2}\| Df(\mathbf{x}_{k})\|^{2}\\
\displaystyle&\displaystyle=f(\mathbf{x}_{k})-\alpha\| Df(\mathbf{x}_{k})\|^{2}+\alpha^{2}\frac{M}{2}\| Df(\mathbf{x}_{k})\|^{2}.\end{aligned} (13.2)

Minimum po prawej stronie przyjmowane jest dla \alpha=1/M. Przypomnijmy również, że \mathbf{x}_{{k+1}} realizuje minimum po \alpha\ge 0 z lewej strony. Zatem

f(\mathbf{x}_{{k+1}})\le f(\mathbf{x}_{k})-\frac{1}{2M}\| Df(\mathbf{x}_{k})\|^{2}.

Odejmijmy od obu stron f({\bar{\mathbf{x}}}) i zastosujmy nierówność \| Df(\mathbf{x}_{k})\|^{2}\ge m\big(f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})\big) wynikającą z lematu 13.1:

f(\mathbf{x}_{{k+1}})-f({\bar{\mathbf{x}}})\le f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})-\frac{m}{2M}\big(f(\mathbf{x}_{k})-f({\bar{\mathbf{x}}})\big).

Po prostym przekształceniu dostajemy tezę.

Rys. 13.1. Wykres funkcji \alpha\mapsto\frac{M}{2}\alpha^{2}-\alpha.

Zajmijmy się regułą minimalizacji ograniczonej. Wówczas \mathbf{x}_{{k+1}} realizuje minimum po lewej stronie (13.2) dla \alpha\in[0,A\|). Minimum po prawej stronie przy ograniczeniu \alpha\le\min(A,\bar{\alpha}) realizowane jest przez \alpha=\gamma, 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 \mathbf{x}_{{k+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 {\bar{\mathbf{x}}}, tj. czym większe m, tym ostrzejsza zależność między normą gradientu a odległością od punktu {\bar{\mathbf{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 \alpha _{k}=\beta^{{m_{k}}}s, gdzie m_{k} jest najmniejszą liczbą całkowitą nieujemną m spełniającą nierówność

f(\mathbf{x}_{k})-f(\mathbf{x}_{k}+\beta^{m}s\,\mathbf{d}_{k})\ge-\sigma\beta^{m}s\; Df(\mathbf{x}_{k})\mathbf{d}_{k}.

Stała s>0 nazywana jest krokiem, \beta reguluje szybkość zmniejszania kroku (czym mniejsza wartość, tym szybciej krok się zmniejsza), zaś \sigma 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ż Df(\mathbf{x}_{k})\mathbf{d}_{k}=-\| Df(\mathbf{x}_{k})\|^{2}:

f(\mathbf{x}_{k})-f\big(\mathbf{x}_{k}-\beta^{m}s\,\big(Df(\mathbf{x}_{k})\big)^{T}\big)\ge\sigma\beta^{m}s\| Df(\mathbf{x}_{k})\|^{2}. (13.3)

Implementacja metody Armijo jest bardzo łatwa. Startujemy z punktu \mathbf{x}_{k}-s\,\big(Df(\mathbf{x}_{k})\big)^{T} i sprawdzamy, czy spełniony jest w nim warunek (13.3). Jeśli tak, to kończymy poszukiwanie. W przeciwnym przypadku, rozważamy punkty \mathbf{x}_{k}-\beta s\,\big(Df(\mathbf{x}_{k})\big)^{T},\ \mathbf{x}_{k}-\beta^{2}s\,\big(Df(\mathbf{x}_{k})\big)^{T},\ldots. W zadaniu 13.3 pokażemy, że w skończonej liczbie kroków znajdziemy punkt spełniający warunek (13.3), jeśli \mathbf{d}_{k}\ne\mathbf{0}. Z nierówności (13.3) wynika, że f(\mathbf{x}_{{k+1}})<f(\mathbf{x}_{k}).

Twierdzenie 13.2

Niech (\mathbf{x}_{k}) będzie ciągiem punktów skonstruowanych przez zastosowanie metody najmniejszego spadku z regułą Armijo.

  1. Jeśli istnieje punkt skupienia {\bar{\mathbf{x}}} tego ciągu, to jest on punktem krytycznym.

  2. Jeśli {\bar{\mathbf{x}}} jest punktem krytycznym i macierz D^{2}f({\bar{\mathbf{x}}}) jest dodatnio określona, to istnieje kula B({\bar{\mathbf{x}}},\varepsilon) o środku {\bar{\mathbf{x}}} i promieniu \varepsilon>0, taka że gdy \mathbf{x}_{k}\in B({\bar{\mathbf{x}}},\varepsilon) dla pewnego k, to ciąg \mathbf{x}_{k} dąży do {\bar{\mathbf{x}}}. W szczególności, jeśli w punkcie skupienia {\bar{\mathbf{x}}} macierz drugich pochodnych jest dodatnio określona, to cały ciąg zmierza do {\bar{\mathbf{x}}}.

Dowód

Dowód pierwszej tezy jest niemal identyczny jak dowód twierdzenia 13.1.

Z faktu, że macierz D^{2}f({\bar{\mathbf{x}}}) jest dodatnio określona wynika, że istnieje kula otwarta B_{1} o środku {\bar{\mathbf{x}}}, taka że f jest wypukła w B_{1}. Możemy również znaleźć kulę otwartą B_{2} o środku w {\bar{\mathbf{x}}} i mniejszym promieniu niż B_{1}, taką że x-s\big(Df(\mathbf{x})\big)^{T}\in B_{1}, jeśli \mathbf{x}\in B_{2}. Wynika to z ciągłości pochodnej Df wokół {\bar{\mathbf{x}}} i z tego, że się ona w {\bar{\mathbf{x}}} zeruje. Ciągłość funkcji f pozwala nam wywnioskować, że istnieje zbiór poziomicowy S=\{\mathbf{x}\in B_{1}:\  f(\mathbf{x})\le\alpha\}, dla pewnego \alpha>f({\bar{\mathbf{x}}}), zawarty w B_{2} (zwróć uwagę, że do S wybieramy punkty z większego zbioru B_{1}, lecz wymagamy by po zastosowaniu warunktu poziomicowego S było zawarte w B_{2}). Zbiór S ma niepuste wnętrze, bo funkcja f jest ciągła i \alpha>f({\bar{\mathbf{x}}}). Ponadto jest on oddzielony od brzegu B_{1}, bo B_{2} ma mniejszy promień. Innymi słowy, jeśli odcinek łączy punkt w S z punktem spoza S, to na tym odcinku jest taki punkt \mathbf{y}, że f(\mathbf{y})>\alpha. Wykorzystamy to zaraz. Niech \mathbf{x}_{k}\in S. Wówczas \mathbf{x}_{{k+1}}\in B_{1} (bo S\subset B_{2}) oraz f(\mathbf{x}_{{k+1}})<f(\mathbf{x}_{k}). Jeśli teraz \mathbf{x}_{{k+1}} nie zawiera się w S, to, jak ustaliliśmy powyżej, na odcinku łączącym \mathbf{x}_{k} z \mathbf{x}_{{k+1}} musi istnieć punkt \mathbf{y}, taki że f(\mathbf{y})>\alpha\ge f(\mathbf{x}_{k})>f(\mathbf{x}_{{k+1}}). Ale cały ten odcinek leży w B_{1}, na którym to zbiorze funkcja f jest wypukła. Nie może więc istnieć na tym odcinku punkt \mathbf{y}, w którym wartość jest większa niż w obu jego końcach. Sprzeczność! Wykazaliśmy tym samym, że \mathbf{x}_{{k+1}}\in S. Czyli od pewnego miejsca ciąg (\mathbf{x}_{k}) pozostaje w S. Jako, że S jest zwarty, to każdy podciąg (\mathbf{x}_{k}) ma w nim punkt skupienia. Z pierwszej częsci twierdzenia wynika, że jest to punkt krytyczny, a takowy może być tylko jeden w B_{1} – jest nim {\bar{\mathbf{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,\beta,\sigma. 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 \mathbf{d} jest kierunkiem spadku w punkcie \mathbf{x}, to istnieje \delta>0, taka że dla \alpha\in(0,\delta) mamy

f(\mathbf{x}+\alpha\mathbf{d})<f(\mathbf{x}).
Ćwiczenie 13.2

Udowodnij lemat 13.1.

Wskazówka: 

Przyjrzyj się dokładnie dowodowi lematu 12.4.

Ćwiczenie 13.3

Wykaż, że jeśli \mathbf{d}_{k}\ne 0, to wartość \alpha _{k} z reguły Armijo można wyznaczyć w skończonej liczbie kroków (choć różnej dla każdego \mathbf{x}_{k}).

Wskazówka: 

Rozważ funkcję g(\alpha)=f(\mathbf{x})-f\big(\mathbf{x}-\alpha\,\big(Df(\mathbf{x})\big)^{T}\big)-\sigma\alpha\| Df(\mathbf{x})\|^{2}. Zastanów się, dlaczego teza nie jest poprawna dla \sigma\ge 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 \mathbf{d}_{k} 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.