MO Moduł 5

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
MO M5 Slajd1.png

MO M5 Slajd2.png

MO M5 Slajd3.png
Powróćmy do naszych rozważań z części drugiej wykładu trzeciego.

Jak pamiętamy, Algorytm jest ślepy — nie może zobaczyć rzeźby trenu na którym się znajduje. Na schodach szedł w prawo, potem w lewo — sprawdzał swoje otoczenie. Teraz otoczenie ma więcej wymiarów, ale pomysł może być ten sam — sprawdzać zachowanie funkcji wyboru w sąsiedztwie punktu , w którym się aktualnie znajduje. Natychmiast pojawia się pytanie — jak duże powinno być to sąsiedztwo? Udzielenie przemyślanej odpowiedzi nie jest zagadnieniem łatwym, ponieważ wielkość przeszukiwanego obszaru ma, intuicyjnie, wpływ, z jednej strony na szybkość znalezienia ekstremum mierzoną ilością sprawdzanych obszarów (im większy tym szybciej), a z drugiej na dokładność Algorytmu (przy ograniczonych możliwościach przeszukiwania — im mniejszy tym dokładniej).


MO M5 Slajd4.png

MO M5 Slajd5.png

MO M5 Slajd6.png
Przeanalizujmy teraz sposób pierwszy, zakładający kompletną niewiedzę o kształcie funkcji wyboru. Oznacza to że z punktów kuli, zaczepionej w „bieżącym” punkcie Algorytm musi wybrać pewną próbę, np. tworząc wielowymiarową siatkę i jej węzły uznać za próbę (podejście deterministyczne), czy też wygenerować próbę losowo, bacząc aby była rozłożona równomiernie (podejście probabilistyczne).

MO M5 Slajd7.png
Algorytm może być:
  • ostrożny (wiem, że schody opadają w prawo, schodzę w prawo jeden stopień) i przyjąć za środek nowego otoczenia
    ,

a następnie przeszukiwać je tak jak poprzednio.


MO M5 Slajd8.png
Algorytm może być też:
  • odważny (wiem, że schody opadają w prawo, skaczę kilka stopni w prawo) i przesunąć środek kuli poszukiwań wzdłuż kierunku wyznaczonego przez różnicę wektorów , tzn. ustalić środek nowej kuli w punkcie
    .

MO M5 Slajd9.png

MO M5 Slajd10.png
Większość algorytmów deterministycznych poszła w zapomnienie, ale do dzisiaj jest używany algorytm wymyślony przez:
J. A. Neldera i R. Meada i opublikowany w 1965 r.

MO M5 Slajd11.png
Nie będziemy zagłębiali się w szczegóły algorytmu Neldera i Meada (jak ustalić próbę początkową, jak będąc odważnym zachować niezbędny stopień ostrożności itd.) odsyłając Czytelnika np. do monografii A. Stachurski, A. Wierzbicki: Podstawy optymalizacji, Oficyna Wydawnicza PW 1999, rozdział 3.10.

MO M5 Slajd12.png
Dla funkcji kwadratowej algorytm Neldera i Meada zachowuje się bardzo ładnie.

MO M5 Slajd13.png
Metody oparte na takim rozumowaniu od połowy lat dziewięćdziesiątych XX w nazywa się:
Metodami obszaru zaufania
(Trust region methods)

MO M5 Slajd14.png
Przyjmujemy zatem, że dookoła punktu bieżącego została określona kula i funkcja będąca modelem zachowania się funkcji wyboru w tej kuli, modelem dużo prostszym w analizie niż funkcja oryginalna. Do określenia modelu możemy posłużyć się intuicją opartą na rozważaniach punktu drugiego, co jak pamiętamy przekłada się na przeświadczenie, że funkcja celu dobrze daje się przybliżyć funkcją kwadratową
(APR)

MO M5 Slajd15.png
W takiej sytuacji przeszukanie otoczenia może oznaczać tylko jedno — szukanie punktu , minimalizującego funkcję modelującą na kuli.
Punkt ten oczywiście będzie się różnił od rzeczywistego minimum funkcji celu na kuli zaufania, ale mamy nadzieję, że niewiele, a co ważniejsze będzie spełniona nierówność
oznaczająca, że funkcja celu z kroku na krok maleje.

MO M5 Slajd16.png
Ponieważ punkt został wygenerowany w oparciu o model, to gdy kula jest za duża, może nie być właściwy — wartość funkcji celu może być w nim większa niż w punkcie centralnym kuli. Oznacza to, że w stosowny sposób trzeba dostosowywać promień kuli do zmienności funkcji celu. Zauważmy też, że przy takim podejściu, aby znaleźć rozwiązanie zadania optymalizacji bez ograniczeń trzeba rozwiązywać wielokrotnie zadanie z ograniczeniami ale z prostą funkcją wyboru — kwadratową funkcją aproksymującą.

MO M5 Slajd17.png
W świetle ostatniej uwagi jest oczywiste, że algorytmy wykorzystujące omawiane podejście mogły liczyć na sukces dopiero w momencie, kiedy opracowano efektywne algorytmy rozwiązywania występujących w nich zadań
Parser nie mógł rozpoznać (nieznana funkcja „\mathrmT”): {\displaystyle f_M(x)=x^{\mathrm T}Qx+c^{\mathrmT}x+\sigma \rightarrow } min
p.o. ,
co nastąpiło w połowie lat siedemdziesiątych ubiegłego wieku.

MO M5 Slajd18.png
Podstawowy algorytm obszaru zaufania

Inicjalizacja
Wybierz punkt początkowy .
Ustal początkowy obszar zaufania .
Podstaw .

Kroki algorytmu

  1. Dla punktu wyznacz model funkcji celu w jego otoczeniu.
  2. Znajdź przybliżenie punktu
    = arg min.
  3. Sprawdź czy wielkość obszaru zaufania została wybrana właściwie. Jeżeli tak, podstaw , idź do 5. W przeciwnym przypadku idź do 4.
  4. Zmniejsz obszar zaufania do , podstaw , idź do 2.
  5. Jeżeli spełnione jest kryterium stopu, to przyjmij za rozwiązanie i stop. W przeciwnym przypadku idź do 6.
  6. Sprawdź czy należy powiększyć obszar zaufania do . Jeżeli tak, podstaw , idź do 7. W przeciwnym przypadku idź do 7.
  7. Podstaw , idź do 1.

Wyjaśnień wymagają kroki 2, 3, 6 i oczywiście kryterium stopu.


MO M5 Slajd19.png

MO M5 Slajd20.png

MO M5 Slajd21.png
Ciąg prostszych zadań daje ciąg rozwiązań {}Parser nie mógł rozpoznać (błąd składni): {\displaystyle _{k = 0}^\infty}} Naturalne pytanie które postawiliśmy, to kiedy go uciąć – które uznać za ostatnie, dające rozwiązanie z dostateczną dokładnością. Był to zasygnalizowany problem testu stopu. Związane z tym problemem jest pytanie drugie – czy wygenerowany ciąg w ogóle jest zbieżny, a gdy jest, to czy jego granica jest rozwiązaniem zadania optymalizacji ? Jest to pytanie teoretyczne i odpowiemy na nie po konkretyzacji algorytmu w wykładzie siódmym.

MO M5 Slajd22.png
Tu oczywistym pomysłem jest wykorzystanie rozważań teoretycznych, pokazujących związek kierunku poprawy z gradientem (lemat 4.3). Algorytm będzie zatem wykorzystywał:
Metody kierunków poprawy

MO M5 Slajd23.png
Gdy znamy gradient, nierówność ta pozwala sprawdzić czy dany kierunek jest kierunkiem poprawy. Mając ustalony kierunek poprawy powinniśmy poruszając się wzdłuż niego znaleźć punkt dający mniejszą niż w punkcie bieżącym wartość funkcji celu.

MO M5 Slajd24.png

MO M5 Slajd25.png
Zgodnie z określeniem poruszania się wzdłuż kierunku, znalezienie punktu jest równoważne ustaleniu pewnego . Zatem zmieniając od zera do plus nieskończoności ruszamy się wzdłuż prostej w kierunku malenia funkcji celu. Konkretną wartość długość kroku – możemy ustalić a priori. Intuicyjnie nie jest to najlepszy sposób, bo żeby zabezpieczyć się przed zbytnim przeskoczeniem minimum funkcji celu na zbiorze trzeba tą stałą długość kroku wybrać niewielką. Wobec tego można postępować tak:

wybieramy duży krok początkowy ,
gdy to uznajemy za długość kroku,
gdy przeciwnie – zmniejszamy do ),
powtarzamy sprawdzenie czy wartość funkcji zmalała, itd. aż uzyskamy krok dający poprawę.


MO M5 Slajd26.png
Dokonujemy, jak mówimy minimalizacji w kierunku. Formułując to zadanie przybliżonej minimalizacji funkcji jednej zmiennej ( i są ustalone!) wykorzystaliśmy fakt, że zbiór dopuszczalny jest określony jednym ograniczeniem równościowym.

Wprawdzie wiemy, że „ruszanie się” wzdłuż kierunku poprawy nie musi doprowadzić do minimum globalnego, ale na pewno poprawi wartość funkcji celu. O ile poprawi ? – Może poprawić bardzo niewiele, ale tak jak przy ustalaniu podstaw poprzednich metod, zgodnie z naszym podejściem optymistycznym, uważamy że ta poprawa będzie istotna. Jak pamiętamy przekonanie to ma podstawy formalne, ponieważ rozważania teoretyczne sugerują, że „porządne” funkcje są lokalnie wypukłe, a co za tym idzie nie powinno być kłopotów ze znalezieniem punktu lepszego niż bieżący. Przy wymyślaniu kryterium stopu pomocny może być warunek stacjonarności gradientu wskazujący na możliwość konstrukcji kryterium stopu w oparciu o jakąś miarę „małości” gradientu.


MO M5 Slajd27.png

MO M5 Slajd28.png

MO M5 Slajd29.png
Bardziej formalnie przedstawioną procedurę minimalizacji opartą na generowaniu kierunków poprawy opisuje następujący podstawowy algorytm kierunków poprawy.

Podstawowy algorytm kierunków poprawy

Inicjalizacja
Wybierz punkt początkowy .
Podstaw .

Kroki algorytmu

  1. Dla punktu wyznacz kierunek poprawy .
  2. Ustal długość kroku w kierunku poprawy .
  3. Wylicz następny punkt podstawiając .
  4. Jeżeli spełnione jest kryterium (test) stopu, to przyjmij za rozwiązanie i stop. W przeciwnym przypadku idź do 5.
  5. Podstaw , idź do 1.

MO M5 Slajd30.png
Teraz zauważmy tylko, że test stopu powinien zawierać dwa warunki: jeden badający “optymalność” kolejnego punktu, a drugi określający maksymalną liczbę iteracji.

MO M5 Slajd31.png

MO M5 Slajd32.png
Szukanie punktu dającego poprawę:
  • w metodzie rozsiewania punktów próbnych jest to zadanie wyboru punktu najmniejszego ze skończonej ich liczby;
  • w metodzie obszarów zaufania jest to zadanie wielo-wymiarowej minimalizacji przy ograniczeniach, najczęściej funkcji kwadratowej, zadanie ZKK;
  • dla metody kierunków poprawy jest to poszukiwanie punktu dającego akceptowalne zmalenie w stosunku do wartości w zerze (punkcie początkowym), odpowiednio określonej funkcji jednej zmiennej, zadanie ZPK.

MO M5 Slajd33.png

MO M5 Slajd34.png
  • Zbieżność skończona, która ma miejsce wtedy gdy istnieje taka liczba dla której . Z punktu widzenia znajdowania rozwiązań zadań optymalizacji wydaje się, że to najlepszy rodzaj zbieżności. Taki rodzaj zbieżności ma algorytm SIMPLEX rozwiązywania zadań liniowych. Jednak jak pamiętamy, liczba iteracji może być bardzo duża, co oznacza, że na rozwiązanie zadania trzeba bardzo długo czekać. Metody punktu wewnętrznego nie mają skończonej zbieżności jednak dają zadowalające przybliżenie rozwiązania dużo szybciej. Dlatego wciąż trwają poszukiwania coraz bardziej skutecznych metod tego typu. A wniosek ogólny – z praktycznego punktu widzenia zbieżność skończona z bardzo dużym może być gorsza niż zbieżność nieskończona, w sytuacji w której ciąg szybko zmierza do niewielkiego otoczenia rozwiązania.
  • Znana Państwu z analizy matematycznej zbieżność wektorowego ciągu nieskończonego, zwana jest w teorii metod optymalizacji krótko zbieżnością (nieskończoną). Jest ona rozumiana dwojako: jako zbieżność do rozwiązania , albo dla funkcji gładkich – zbieżność do punktu stacjonarnego gradientu, tzn. takiego wektora , że
    .
    Jak pamiętamy punkt może być punktem lokalnego minimum, maksimum albo lokalne zachowanie funkcji w różnych kierunkach może być różne, np. może to być punkt siodłowy albo punkt przegięcia. Ten ostatni przypadek pokazuje rysunek na następnej stronie.
  • Dlatego w niektórych wypadkach twórcom algorytmów udaje się udowodnić własność jeszcze słabszą: ciąg wektorów generowany przez algorytm zawiera podciąg zbieżny. Akceptacja zbieżności tego rodzaju po pokazaniu na przykładach, że algorytm w rozsądnej liczbie kroków (iteracji) znajduje dobre przybliżenie rozwiązania mieści się w przyjętym “optymistycznym” podejściu do analizy sytuacji.

MO M5 Slajd35.png
W tym przypadku rozwiązaniem równania jest , a ten punkt ekstremum, nawet lokalnym, dla rozważanej funkcji nie jest. Jednak nasze optymistyczne podejście pozwala przyjąć, że przypadki takie jak przedstawiony, są bardzo rzadkie.

MO M5 Slajd36.png

MO M5 Slajd37.png
Zbieżny ciąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{x^{(k)}\}^\infty_{k=0}}} otrzymany w kolejnych krokach algorytmu, jest zbieżny

a) liniowo, gdy dodatkowo

lim,

b) superliniowo, gdy dodatkowo

lim,

c) kwadratowo, gdy dodatkowo

lim.

Definicje szybkości związane są z szybkością zbiegania do zera:

postępu geometrycznego o dodatnim ilorazie mniejszym niż jeden, np. danego wzorem

, bo zbieżność liniowa,

np. ciągu danego wzorem

, bo zbieżność superliniowa,

np. ciągu danego wzorem

, bo zbieżność kwadratowa.


MO M5 Slajd38.png
Na rysunku przedstawiono w skali logarytmicznej siedem pierwszych wyrazów wymienionych wyżej ciągów.

Widać że zbieżność liniowa jest najwolniejsza, a kwadratowa - najszybsza. Różne eksperymenty pokazały, że w zastosowaniach praktycznych szybkość liniowa jest do zaakceptowania gdy granica jest dostatecznie mała, nie większa niż .


MO M5 Slajd39.png

MO M5 Slajd40.png
Pierwszy sposób został omówiony dokładnie w wykładzie poprzednim. Została pokazana ograniczoność możliwości jego stosowania. Ogólna zasada działania pozostałych trzech schematów jest taka sama i polega na naprzemiennym rozwiązywaniu dwu zadań: generacji zbioru podlegającego przeszukaniu i szukaniu w tym zbiorze punktu dającego poprawę (np. minimalizującego odpowiednio dobraną funkcję). W metodzie obszarów zaufania to zadanie poprawy jest wielowymiarową minimalizacją przy ograniczeniach, najczęściej funkcji kwadratowej. Dla metody kierunków poprawy jest to poszukiwanie punktu dającego akceptowalne zmalenie w stosunku do wartości w zerze (punkcie początkowym), odpowiednio określonej funkcji jednej zmiennej. Schematy te zostały przedstawione ogólnie i dla zastosowań praktycznych wymagają „doprecyzowania”. Zostanie to uczynione w następnych wykładach.

MO M5 Slajd41.png

MO M5 Slajd42.png