Zagadnienia

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 WRn będzie zbiorem wypukłym. Funkcję f:WR nazywamy ściśle quasi-wypukłą, jeśli dla dowolnych x,yW, xy oraz λ0,1 zachodzi

fλx+1-λy<maxfx,fy.

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

Lemat 12.1

  1. Funkcja quasi-wypukła ma co najwyżej jedno minimum (lokalne i globalne).

  2. Funkcja ściśle wypukła jest ściśle quasi-wypukła.

  3. 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 x¯ w jej dziedzinie o tej własności, że funkcja jest ściśle malejąca dla xx¯ i ściśle rosnąca dla xx¯.

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,bR będzie funkcją ściśle quasi-wypukłą i axyb.

  1. Jeśli fxfy, to fz>fy dla każdego za,x.

  2. Jeśli fxfy, to fz>fx dla każdego zy,b.

Dowód

Udowodnimy punkt (1) przez sprzeczność. Przypuśćmy, że istnieje za,x o tej własności, że fzfy. Wówczas z quasi-wypukłości f wynika, że fx<maxfz,fy=fy, co przeczy założeniu, że fxfy. 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,bR wybieramy mały ε>0 i porównujemy wartości w punktach a+b2-ε i a+b2+ε (patrz rys. 12.1). Jeśli fa+b2-εfa+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 fxk+yk2-εkfxk+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 c0,1, taka że

yk-xkb-ack.

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.

12.2. Metoda Newtona

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

fyfx+fxy-x+12f′′xy-x.

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

y=x-fxf′′x.

Zauważmy, że jeśli w punkcie x zeruje się pochodna fx, 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-fxkf′′xk

  • Koniec: gdy fxk+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.

Lemat 12.3

Załóżmy, że f jest funkcją klasy C2 na otoczeniu minimum lokalnego x¯ oraz f′′x¯>0. Wówczas istnieje δ>0, taka że dla xkBx¯,δ mamy

xk+1-x¯12xk-x¯.
Dowód

Z ciągłości f′′ na otoczeniu x¯ oraz z tego, że f′′x¯>0 wynika istnienie δ>0 o następującej własności:

f′′x-f′′yf′′x12dla x,yBx¯,δ.(12.1)

Załóżmy, że xkBx¯,δ. Z definicji xk+1 dostajemy

xk+1-x¯=xk-x¯-fxkf′′xk=xk-x¯-fxk-fx¯f′′xk,

gdzie w ostatniej równości skorzystaliśmy z równości fx¯=0. Sprowadzamy prawą stronę do wspólnego mianownika i stosujemy twierdzenie o wartości średniej do różnicy pochodnych:

xk+1-x¯=1f′′xkf′′xkxk-x¯-fxk-fx¯=1f′′xkf′′xk-f′′θkxk-x¯,

gdzie θk należy do przedziału o końcach w x¯ i xk. Obkładamy obie strony wartością bezwzględną i stosujemy oszacowanie (12.1) dla x=xk i y=θk.

Wniosek 12.1

Przy założeniach powyższego lematu, jeśli xkBx¯,δ to xlBx¯,δ dla wszystkich lk.

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 x¯ będzie minimum lokalnym funkcji f. Załóżmy, że na przedziale U zawierającym x¯ w swoim wnętrzu funkcja f jest dwukrotnie różniczkowalna (niekoniecznie klasy C2) oraz

infxUf′′(x)=:m>0.

Wówczas dla każdego xU mamy

x-x¯fxm,fx-fx¯fx2m.
Dowód

Ustalmy xU. Stosujemy tw. Taylora, tw. 1.10, dwukrotnie (przypomnijmy, że fx¯=0):

fx=fx¯+12f′′θ1x-x¯2,
fx¯=fx+fxx¯-x+12f′′θ2x¯-x2,

gdzie θ1,θ2 leżą w przedziale o końcach x¯ i x, a więc również w przedziale U. Podstawiamy pierwsze równanie do drugiego:

-fxx¯-x=f′′θ1+f′′θ22x-x¯2.

Obkładamy obydwie strony modułem i dzielimy przez x-x¯ dostając

fx=f′′θ1+f′′θ22x-x¯.

Przypomnijmy, że druga pochodna f′′ jest ograniczona z dołu przez m na U. Zatem fxmx-x¯, skąd pierwsza część tezy wynika natychmiastowo.

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

fx¯-fx=fxx¯-x+12f′′θ2x¯-x2fxx¯-x+m2x¯-x2fxx¯-x,

gdzie ostatnia nierówność wynika z tego, że m0. 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-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 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].

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 xk,yk zmniejsza się w sposób wykładniczy, tzn. istnieje stała c0,1, taka że

yk-xkb-ack.
Ćwiczenie 12.4

Podaj przykład funkcji f:RR oraz punktu startowego x0, 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ń:

fx-fx¯fx22m.
Wskazówka: 

Przeprowadź dowód bez użycia oszacowania na x-x¯. Skorzystaj oczywiście z twierdzenia Taylora.

Ćwiczenie 12.6

Opracuj szybki algorytm minimalizowania funkcji wypukłej f:RR klasy C1.

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.