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

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

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:

Idea algorytmu jest bardzo prosta. Szukając minimum funkcji ściśle quasi-wypukłej f:a,b→R wybieramy mały ε>0 i porównujemy wartości w punktach a+b2-ε i a+b2+ε (patrz rys. 12.1). Jeśli f⁢a+b2-ε≥f⁢a+b2+ε, to minimum znajduje się w przedziale a+b2-ε,b. W przeciwnym przypadku jest ono w przedziale a,a+b2+ε.

Algorytm wygląda następująco:

• Inicjalizacja: Wybierz 0<ε0<a+b2. Połóż x0=a, y0=b.

• Krok k-ty:

  1. Jeśli f⁢xk+yk2-εk≥f⁢xk+yk2+εk, to xk+1=xk+yk2-εk i yk+1=yk.

  2. W przeciwnym przypadku xk+1=xk oraz yk+1=xk+yk2+εk.

  3. εk+1=εk/2.

• Koniec: gdy różnica yk+1-xk+1 jest dostatecznie mała.

Załóżmy, że istnieje minimum 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 xk,yk dla każdego k. Długość tego przedziału dąży do zera, co pociąga zbieżność zarówno xk jak i yk do rozwiązania 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 xk+1,yk+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 xk,yk zmniejsza się wykładniczo szybko, tzn. istnieje stała c∈0,1, taka że

Pamiętając, że rozwiązanie x¯ leży w tym przedziale dla każdego k, wnioskujemy, iż zbieżność xk i yk do rozwiązania x¯ jest wykładnicza.

Metoda Newtona służy do znajdowania zer funkcji różniczkowalnej. Stosując ją do funkcji g⁢x=f′⁢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:R→R jest dwukrotnie różniczkowalna. Przybliżamy ją wokół punktu x za pomocą wielomianu Taylora drugiego stopnia:

Zamiast minimalizować funkcję f szukamy minimum jej przybliżenia. Aby miało to sens musimy założyć, że f′′⁢x≠0. Różniczkując prawą stronę po y dostajemy wzór na punkt krytyczny przybliżenia Taylora:

Zauważmy, że jeśli w punkcie x zeruje się pochodna f′⁢x, to y=x. To daje nadzieję na poprawność podejścia. Dokładniejsze wyniki podamy po zapisaniu algorytmu:

• Inicjalizacja: Wybierz punkt początkowy x0 i dokładność ε>0.

• Krok k-ty: xk+1=xk-f′⁢xkf′′⁢xk

• Koniec: gdy f′⁢xk+1≤ε.

Powyższy algorytm niesie ze sobą wiele wątpliwości. Po pierwsze, nie jest wcale jasne, czy ciąg xk 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 x0 może spowodować, że ciąg xk 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.

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.

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 x0,ε 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].