Zagadnienia

12.1 Optymalizacja bez użycia pochodnych
12.2 Metoda Newtona
12.3 Zadania

12. Metody numeryczne. Optymalizacja bez ograniczeń

W poprzednich rozdziałach budowaliśmy teorię służącą rozwiązywaniu problemów optymalizacyjnych. By być bardziej precyzyjnym, dowiedliśmy twierdzeń, które ułatwiają znalezienie kandydatów na rozwiązania oraz stwierdzenie, czy któryś z nich jest rozwiązaniem. Niestety w obu tych krokach musimy rozwiązywać układy równań nieliniowych. W praktycznych zadaniach optymalizacyjnych układy te mogą nie mieć ”ładnych” rozwiązań lub po prostu nie jesteśmy w stanie ich znaleźć w sposób analityczny. Pozostaje wówczas zastosowanie metod numerycznych, które pozwolą na przybliżenie rozwiązania. W tym i kolejnych rozdziałach opiszemy kilka takich algorytmów numerycznych. Algorytmy te będą raczej atakowały problem optymalizacyjny bezpośrednio (tzn. nie będziemy się starali znaleźć zbioru punktów spełniających warunek konieczny pierwszego rzędu). Będą one krok po kroku tworzyły ciąg punktów zbiegający do rozwiązania. Nie oznacza to jednak, że mnożniki Lagrange'a i metody dualne są nieprzydatne przy tworzeniu algorytmów numerycznych. Wręcz przeciwnie. W przypadku ograniczeń równościowych klasyczne podejście wiedzie właśnie poprzez mnożniki Lagrange'a (tzw. metoda mnożników Lagrange'a), patrz monografie Bazaraa, Sherali, Shetty [3] oraz Bertsekas [4, 5]. My jednak pójdziemy inną drogą, gdyż możemy poświęcić optymalizacji z ograniczeniami zaledwie jeden rozdział.

Na kolejnych stronach będziemy opisywać algorytmy optymalizacyjne oraz analizować ich działanie. Ta analiza powinna zawierać następujące punkty:

zbieżność do rozwiązania (poprawność algorytmu),
warunek końca (kiedy możemy przerwać wykonywanie programu, ponieważ znaleziony punkt jest dostatecznie blisko rozwiązania),
szybkość zbieżności do rozwiązania.

W tym rozdziale opiszemy metody optymalizacyjne na prostej. Będą one konieczne do zaimplementowania algorytmów optymalizacyjnych w wyższym wymiarze, którymi zajmiemy się w roz. 13. Zadania z ograniczeniami rozważymy w roz. 14.

12.1. Optymalizacja bez użycia pochodnych

Zanim przejdziemy do dyskusji właściwego algorytmu, wprowadzimy pojęcie funkcji ściśle quasi-wypukłej i jej własności.

Definicja 12.1

Niech $W\subset\mathbb{R}^{n}$ będzie zbiorem wypukłym. Funkcję $f:W\to\mathbb{R}$ nazywamy ściśle quasi-wypukłą, jeśli dla dowolnych $\mathbf{x},\mathbf{y}\in W$ , $\mathbf{x}\ne\mathbf{y}$ oraz $\lambda\in(0,1)$ zachodzi

$f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y})<\max\big(f(\mathbf{x}),f(\mathbf{y})\big).$

Dowód poniższych własności funkcji quasi-wypukłych pozostawiamy jako ćwiczenie.

Lemat 12.1

Funkcja quasi-wypukła ma co najwyżej jedno minimum (lokalne i globalne).
Funkcja ściśle wypukła jest ściśle quasi-wypukła.
Funkcja określona na prostej lub otwartym przedziale jest ściśle quasi-wypukła jeśli jest ściśle malejąca, ściśle rosnąca lub istnieje punkt $\bar{x}$ w jej dziedzinie o tej własności, że funkcja jest ściśle malejąca dla $x\le\bar{x}$ i ściśle rosnąca dla $x\ge\bar{x}$ .

Okazuje się, że własność ścisłej quasi-wypukłości pozwala na skonstruowanie algorytmu znajdowania minimum funkcji na domkniętym odcinku bez wykorzystania pochodnych. Główna obserwacja znajduje się w poniższym lemacie:

Lemat 12.2

Niech $f:[a,b]\to\mathbb{R}$ będzie funkcją ściśle quasi-wypukłą i $a\le x\le y\le b$ .

Jeśli $f(x)\ge f(y)$ , to $f(z)>f(y)$ dla każdego $z\in[a,x).$
Jeśli $f(x)\le f(y)$ , to $f(z)>f(x)$ dla każdego $z\in(y,b].$

Dowód

Udowodnimy punkt (1) przez sprzeczność. Przypuśćmy, że istnieje $z\in[a,x)$ o tej własności, że $f(z)\le f(y)$ . Wówczas z quasi-wypukłości $f$ wynika, że $f(x)<\max\big(f(z),f(y)\big)=f(y)$ , co przeczy założeniu, że $f(x)\ge f(y).$ Dowód punktu (2) jest analogiczny.

∎

Rys. 12.1. Podział odcinka.

Idea algorytmu jest bardzo prosta. Szukając minimum funkcji ściśle quasi-wypukłej $f:[a,b]\to\mathbb{R}$ wybieramy mały $\varepsilon>0$ i porównujemy wartości w punktach $\frac{a+b}{2}-\varepsilon$ i $\frac{a+b}{2}+\varepsilon$ (patrz rys. 12.1). Jeśli $f\big(\frac{a+b}{2}-\varepsilon\big)\ge f\big(\frac{a+b}{2}+\varepsilon\big)$ , to minimum znajduje się w przedziale $\big[\frac{a+b}{2}-\varepsilon,b\big]$ . W przeciwnym przypadku jest ono w przedziale $\big[a,\frac{a+b}{2}+\varepsilon\big].$

Algorytm wygląda następująco:

Inicjalizacja: Wybierz $0<\varepsilon _{0}<\frac{a+b}{2}.$ Połóż $x_{0}=a$ , $y_{0}=b$ .
Krok $k$ -ty:
1. Jeśli $f\big(\frac{x_{k}+y_{k}}{2}-\varepsilon _{k}\big)\ge f\big(\frac{x_{k}+y_{k}}{2}+\varepsilon _{k}\big)$ , to $x_{{k+1}}=\frac{x_{k}+y_{k}}{2}-\varepsilon _{k}$ i $y_{{k+1}}=y_{k}$ .
2. W przeciwnym przypadku $x_{{k+1}}=x_{k}$ oraz $y_{{k+1}}=\frac{x_{k}+y_{k}}{2}+\varepsilon _{k}.$
3. $\varepsilon _{{k+1}}=\varepsilon _{k}/2$ .
Koniec: gdy różnica $y_{{k+1}}-x_{{k+1}}$ jest dostatecznie mała.

Załóżmy, że istnieje minimum $\bar{x}$ funkcji $f$ na przedziale $[a,b]$ (tak być nie musi, patrz zadanie 12.2). Na mocy lematu 12.2 minimum to leży w przedziale $[x_{k},y_{k}]$ dla każdego $k.$ Długość tego przedziału dąży do zera, co pociąga zbieżność zarówno $(x_{k})$ jak i $(y_{k})$ do rozwiązania $\bar{x}.$ Dowiedliśmy zatem poprawności algorytmu.

Jeśli zatrzymamy się w kroku $k$ -tym, to dokładność wyznaczenia punktu minimum zadana jest przez długość przedziału $(x_{{k+1}},y_{{k+1}})$ . Uzasadnia to wybór warunku końca. Niestety, ze względu na brak założeń dotyczących różniczkowalności, nie możemy nic powiedzieć, jak dokładnie przybliżamy wartość funkcji w punkcie minimum.

W zadaniu 12.3 pokażemy, że długość przedziału $(x_{k},y_{k})$ zmniejsza się wykładniczo szybko, tzn. istnieje stała $c\in(0,1)$ , taka że

$y_{k}-x_{k}\le(b-a)c^{k}.$

Pamiętając, że rozwiązanie $\bar{x}$ leży w tym przedziale dla każdego $k$ , wnioskujemy, iż zbieżność $x_{k}$ i $y_{k}$ do rozwiązania $\bar{x}$ jest wykładnicza.

12.2. Metoda Newtona

Metoda Newtona służy do znajdowania zer funkcji różniczkowalnej. Stosując ją do funkcji $g(x)=f^{{\prime}}(x)$ możemy znaleźć miejsce zerowania się pochodnej funkcji $f$ lub inaczej punkt krytyczny. Jeśli $f$ jest pseudowypukła, to punkt krytyczny pokrywa się z minimum funkcji. W pozostałych przypadkach, znaleziony punkt może być tylko punktem przegięcia funkcji.

Dla przypomnienia wyprowadzimy metodę Newtona dla znajdowania minimum funkcji. Załóżmy, że funkcja $f:\mathbb{R}\to\mathbb{R}$ jest dwukrotnie różniczkowalna. Przybliżamy ją wokół punktu $x$ za pomocą wielomianu Taylora drugiego stopnia:

$f(y)\approx f(x)+f^{{\prime}}(x)(y-x)+\frac{1}{2}f^{{\prime\prime}}(x)(y-x).$

Zamiast minimalizować funkcję $f$ szukamy minimum jej przybliżenia. Aby miało to sens musimy założyć, że $f^{{\prime\prime}}(x)\ne 0$ . Różniczkując prawą stronę po $y$ dostajemy wzór na punkt krytyczny przybliżenia Taylora:

$y=x-\frac{f^{{\prime}}(x)}{f^{{\prime\prime}}(x)}.$

Zauważmy, że jeśli w punkcie $x$ zeruje się pochodna $f^{{\prime}}(x)$ , to $y=x$ . To daje nadzieję na poprawność podejścia. Dokładniejsze wyniki podamy po zapisaniu algorytmu:

Inicjalizacja: Wybierz punkt początkowy $x_{0}$ i dokładność $\varepsilon>0$ .
Krok $k$ -ty: $\displaystyle x_{{k+1}}=x_{k}-\frac{f^{{\prime}}(\mathbf{x}_{k})}{f^{{\prime\prime}}(x_{k})}$
Koniec: gdy $|f^{{\prime}}(x_{{k+1}})|\le\varepsilon$ .

Powyższy algorytm niesie ze sobą wiele wątpliwości. Po pierwsze, nie jest wcale jasne, czy ciąg $(x_{k})$ ma granicę. Co więcej, łatwo znaleźć niezdegenerowany przykład, żeby był on rozbieżny (patrz zadanie 12.4). Rozumiemy przez to, że funkcja przyjmuje minimum globalne w pewnym punkcie, lecz nieodpowiedni wybór punktu początkowego $x_{0}$ może spowodować, że ciąg $(x_{k})$ zbiega do nieskończoności. W poniższym lemacie pokazujemy warunek dostateczny, aby taki przypadek nie miał miejsca. Co więcej, w lemacie tym podajemy warunki dostateczne tego, by zbieżność do minimum lokalnego była wykładniczo szybka.

Lemat 12.3

Załóżmy, że $f$ jest funkcją klasy $C^{2}$ na otoczeniu minimum lokalnego $\bar{x}$ oraz $f^{{\prime\prime}}(\bar{x})>0$ . Wówczas istnieje $\delta>0$ , taka że dla $x_{k}\in B(\bar{x},\delta)$ mamy

$|x_{{k+1}}-\bar{x}|\le\frac{1}{2}|x_{k}-\bar{x}|.$

Dowód

Z ciągłości $f^{{\prime\prime}}$ na otoczeniu $\bar{x}$ oraz z tego, że $f^{{\prime\prime}}(\bar{x})>0$ wynika istnienie $\delta>0$ o następującej własności:

$\Big|\frac{f^{{\prime\prime}}(x)-f^{{\prime\prime}}(y)}{f^{{\prime\prime}}(x)}\Big|\le\frac{1}{2}\qquad\text{dla $x,y\in B(\bar{x},\delta).$}$

(12.1)

Załóżmy, że $x_{k}\in B(\bar{x},\delta)$ . Z definicji $x_{{k+1}}$ dostajemy

$x_{{k+1}}-\bar{x}=x_{k}-\bar{x}-\frac{f^{{\prime}}(x_{k})}{f^{{\prime\prime}}(x_{k})}=x_{k}-\bar{x}-\frac{f^{{\prime}}(x_{k})-f^{{\prime}}(\bar{x})}{f^{{\prime\prime}}(x_{k})},$

gdzie w ostatniej równości skorzystaliśmy z równości $f^{{\prime}}(\bar{x})=0$ . Sprowadzamy prawą stronę do wspólnego mianownika i stosujemy twierdzenie o wartości średniej do różnicy pochodnych:

$x_{{k+1}}-\bar{x}=\frac{1}{f^{{\prime\prime}}(x_{k})}\big[f^{{\prime\prime}}(x_{k})(x_{k}-\bar{x})-f^{{\prime}}(x_{k})-f^{{\prime}}(\bar{x})\big]=\frac{1}{f^{{\prime\prime}}(x_{k})}\big[f^{{\prime\prime}}(x_{k})-f^{{\prime\prime}}(\theta _{k})\big](x_{k}-\bar{x}),$

gdzie $\theta _{k}$ należy do przedziału o końcach w $\bar{x}$ i $x_{k}$ . Obkładamy obie strony wartością bezwzględną i stosujemy oszacowanie (12.1) dla $x=x_{k}$ i $y=\theta _{k}$ .

∎

Wniosek 12.1

Przy założeniach powyższego lematu, jeśli $x_{k}\in B(\bar{x},\delta)$ to $x_{l}\in B(\bar{x},\delta)$ dla wszystkich $l\ge k$ .

Drugą bolączką metody Newtona jest to, iż zbiega ona do punktu krytycznego, który może również wyznaczać maksimum lokalne lub punkt przegięcia. Założenie pseudowypukłości funkcji $f$ gwarantuje, że punkt krytyczny jest minimum. W pozostałych przypadkach należy zbadać zachowanie funkcji w otoczeniu znalezionego numerycznie punktu krytycznego i na tej podstawie ustalić, czy jest w nim minimum, maksimum lub punkt przegięcia.

Pozostaje jeszcze pytanie o warunek końca. Poniższy lemat podaje jego uzasadnienie.

Lemat 12.4

Niech $\bar{x}$ będzie minimum lokalnym funkcji $f$ . Załóżmy, że na przedziale $U$ zawierającym $\bar{x}$ w swoim wnętrzu funkcja $f$ jest dwukrotnie różniczkowalna (niekoniecznie klasy $C^{2}$ ) oraz

$\inf _{{x\in U}}f^{{\prime\prime}}(x)=:m>0.$

Wówczas dla każdego $x\in U$ mamy

$|x-\bar{x}|\le\frac{|f^{{\prime}}(x)|}{m},\qquad f(x)-f(\bar{x})\le\frac{\big(f^{{\prime}}(x)\big)^{2}}{m}.$

Dowód

Ustalmy $x\in U$ . Stosujemy tw. Taylora, tw. 1.10, dwukrotnie (przypomnijmy, że $f^{{\prime}}(\bar{x})=0$ ):

		$\displaystyle f(x)=f(\bar{x})+\frac{1}{2}f^{{\prime\prime}}(\theta _{1})(x-\bar{x})^{2},$
		$\displaystyle f(\bar{x})=f(x)+f^{{\prime}}(x)(\bar{x}-x)+\frac{1}{2}f^{{\prime\prime}}(\theta _{2})(\bar{x}-x)^{2},$

gdzie $\theta _{1},\theta _{2}$ leżą w przedziale o końcach $\bar{x}$ i $x$ , a więc również w przedziale $U$ . Podstawiamy pierwsze równanie do drugiego:

$-f^{{\prime}}(x)(\bar{x}-x)=\frac{f^{{\prime\prime}}(\theta _{1})+f^{{\prime\prime}}(\theta _{2})}{2}(x-\bar{x})^{2}.$

Obkładamy obydwie strony modułem i dzielimy przez $|x-\bar{x}|$ dostając

$|f^{{\prime}}(x)|=\frac{f^{{\prime\prime}}(\theta _{1})+f^{{\prime\prime}}(\theta _{2})}{2}|x-\bar{x}|.$

Przypomnijmy, że druga pochodna $f^{{\prime\prime}}$ jest ograniczona z dołu przez $m$ na $U$ . Zatem $|f^{{\prime}}(x)|\ge m|x-\bar{x}|$ , skąd pierwsza część tezy wynika natychmiastowo.

Drugą nierówność lematu uzyskujemy znów ze wzoru Taylora:

$f(\bar{x})-f(x)=f^{{\prime}}(x)(\bar{x}-x)+\frac{1}{2}f^{{\prime\prime}}(\theta _{2})(\bar{x}-x)^{2}\ge f^{{\prime}}(x)(\bar{x}-x)+\frac{m}{2}(\bar{x}-x)^{2}\ge f^{{\prime}}(x)(\bar{x}-x),$

gdzie ostatnia nierówność wynika z tego, że $m\ge 0$ . Dowód kończymy mnożąc obie strony nierówności przez $-1$ , obkładając modułem i wstawiając uzyskane wcześniej oszacowanie na $|x-\bar{x}|$ .

∎

Zwróćmy uwagę, że wszystkie matematyczne wyniki dla metody Newtona zakładają dodatniość drugiej pochodnej, a zatem ścisłą wypukłość. W pozostałych przypadkach ocena wyników i dobór parametrów $x_{0},\varepsilon$ pozostaje powierzyć intuicji i doświadczeniom. Nie przeszkadza to wszakże w powszechnym stosowaniu metody Newtona i jej różnych modyfikacji. Zainteresowany czytelnik znajdzie dużo więcej informacji w monografii D. Bertsekas'a [4].

12.3. Zadania

Ćwiczenie 12.1

Udowodnij lemat 12.1

Ćwiczenie 12.2

Znajdź przykład funkcji ściśle quasi-wypukłej określonej na przedziale domkniętym, która nie przyjmuje swojego infimum, czyli zadanie minimalizacyjne nie ma rozwiązania.

Ćwiczenie 12.3

Wykaż, że w metodzie optymalizacji bez użycia pochodnych długość przedziału $[x_{k},y_{k}]$ zmniejsza się w sposób wykładniczy, tzn. istnieje stała $c\in(0,1)$ , taka że

$y_{k}-x_{k}\le(b-a)c^{k}.$

Ćwiczenie 12.4

Podaj przykład funkcji $f:\mathbb{R}\to\mathbb{R}$ oraz punktu startowego $x_{0}$ , takich żeby ciąg generowany przez metodę Newtona nie miał granicy. Dodatkowo wymagamy, aby funkcja $f$ miała minimum globalne w $0$ .

Wskazówka:

Rozważ funkcję malejącą przy $x$ dążącym do nieskończoności.

Ćwiczenie 12.5

Udowodnij, że teza lematu 12.3 może zostać wzmocniona bez zmiany założeń:

$f(x)-f(\bar{x})\le\frac{\big(f^{{\prime}}(x)\big)^{2}}{2m}.$

Wskazówka:

Przeprowadź dowód bez użycia oszacowania na $|x-\bar{x}|$ . Skorzystaj oczywiście z twierdzenia Taylora.

Ćwiczenie 12.6

Opracuj szybki algorytm minimalizowania funkcji wypukłej $f:\mathbb{R}\to\mathbb{R}$ klasy $C^{1}$ .

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

Optymalizacja II

Zagadnienia

12. Metody numeryczne. Optymalizacja bez ograniczeń

12.1. Optymalizacja bez użycia pochodnych

Definicja 12.1

Lemat 12.1

Lemat 12.2

Dowód

12.2. Metoda Newtona

Lemat 12.3

Dowód

Wniosek 12.1

Lemat 12.4

Dowód

12.3. Zadania

Ćwiczenie 12.1

Ćwiczenie 12.2

Ćwiczenie 12.3

Ćwiczenie 12.4

Ćwiczenie 12.5

Ćwiczenie 12.6