MO Moduł 5

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 x, 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).

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 x(k) 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).

Algorytm może być:

• ostrożny (wiem, że schody opadają w prawo, schodzę w prawo jeden stopień) –przyjąć xM(k) za środek nowego otoczenia

$x^{(k + 1)} = x^{M (k)} = α (x^{M (k)} - x^{(} k)) + x^{(k)}, α = 1$

i przeszukiwać je tak jak poprzednio.

Algorytm może być też:

odważny (wiem, że schody opadają w prawo, skaczę kilka stopni w prawo)
- przesunąć środek kuli poszukiwań wzdłuż kierunku wyznaczonego przez różnicę wektorów $x^{M (k)} - x^{k} = d$ , tzn. ustalić środek nowej kuli w punkcie

$x^{M (k)} = α (x^{M (k)} - x^{(} k)) + x^{(k)}, α > 1$

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.

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.

Dla funkcji kwadratowej algorytm Neldera i Meada zachowuje się bardzo ładnie.

Metody oparte na takim rozumowaniu od połowy lat dziewięćdziesiątych XX w nazywa się:

Metodami obszaru zaufania (Trust region methods)

Przyjmujemy zatem, że dookoła punktu bieżącego

x^{(} k)

została określona kula

𝕂 (x, r)

i funkcja

x \mapsto f_{M} (x)

będąca modelem zachowania się funkcji wyboru f 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ą

$(A P R) x \mapsto x^{T} Q x + c^{T} x + σ$

W takiej sytuacji przeszukanie otoczenia może oznaczać tylko jedno – szukanie punktu

x^{M (k)}

, minimalizującego funkcję modelującą na kuli.

Punkt ten oczywiście będzie się różnił od rzeczywistego minimum funkcji celu f na kuli zaufania, ale mamy nadzieję, że niewiele, a co ważniejsze będzie spełniona nierówność

$f (x^{M (k)} < f (x^{k - 1})$

oznaczająca, że funkcja celu z kroku na krok maleje.

Ponieważ punkt

x^{M (k)}

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ą.

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ń

$f_{M} (x) = x^{T} Q x + c^{T} x + σ \to m i n$

$p . o . (x - x^{(k)})^{T} (x - x^{(} k)) \leq r^{2}$

Podstawowy algorytm obszaru zaufania

Inicjalizacja Wybierz punkt początkowy $x^{(0)}$ . Ustal początkowy obszar zaufania $T (x^{(0)}$ ). Podstaw k := 0.

Kroki algorytmu

Dla punktu $x^{(k)}$ wyznacz model f $M (\cdot; x^{(k)})$ funkcji celu w jego otoczeniu.
Znajdź przybliżenie punktu ${\tilde{x}}^{(k)}$
Sprawdź czy wielkość obszaru zaufania została wybrana właściwie. Jeżeli tak, podstaw Parser nie mógł rozpoznać (nieznana funkcja „\tildex”): {\displaystyle \tildex^{(k)}:={x}^{(k)}} , idź do 5. W przeciwnym przypadku idź do 4.
Zmniejsz obszar zaufania do TS, podstaw $T (x^{(k)}) : = T S$ , idź do 2.
Jeżeli spełnione jest kryterium stopu, to $x^{(k)}$ przyjmij za rozwiązanie i stop. W przeciwnym przypadku idź do 6.
Sprawdź czy należy powiększyć obszar zaufania do TL. Jeżeli tak, podstaw

$T (x^{(k)}) : = T L$ , idź do 7. W przeciwnym przypadku idź do 7.

Podstaw k := k + 1, idź do 1.

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

Ciąg prostszych zadań daje ciąg rozwiązań

x_{k - 0}^{(k)}^{\infty}

Naturalne pytanie które postawiliśmy, to kiedy go uciąć – które k 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.

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

Gdy znamy gradient, nierówność ta pozwala sprawdzić czy dany kierunek d 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.

Zgodnie z określeniem poruszania się wzdłuż kierunku, znalezienie punktu

\bar{x} \in P (x^{(k)}; d) \subset R^{n}

jest równoważne ustaleniu pewnego

\bar{α} \in R

Zatem zmieniając

α

od zera do plus nieskończoności ruszamy się wzdłuż prostej

P (x^{(k)}; d)

w kierunku malenia funkcji celu. Konkretną wartość

\bar{α}

– 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 P(x(k);d) trzeba tą stałą długość kroku wybrać niewielką. Wobec tego można postępować tak: wybieramy duży krok początkowy