Kryterium zatrzymania dla miodu Neldera

11

Próbuję zaimplementować algorytm Neldera-Meada do optymalizacji funkcji. Strona wikipedii o Nelder-Mead jest zaskakująco jasna na temat całego algorytmu, z wyjątkiem kryterium zatrzymania. Tam niestety mówi:

Sprawdź zbieżność _{[potrzebne wyjaśnienie]} .

Sam wypróbowałem i przetestowałem kilka kryteriów:

Przestań, jeśli gdzie jest mały i gdzie jest wierzchołkiem simpleksa, uporządkowanym od niskiego ( ) do wysokiego ( ) wartości funkcji. Innymi słowy, gdy maksymalna wartość simpleks jest prawie równa wartości minimalnej. Odkryłem, że to nie działało poprawnie, ponieważ nie daje to żadnych gwarancji co do działania funkcji w simpleksie. Przykład: rozważ funkcję: Optymalizacja jest trywialna, ale załóżmy, że robimy to za pomocą NM, i niech nasze dwa punkty simpleks będą i $f(x_{N+1}) - f(x_1) < \epsilon$ $\epsilon$ $x_i$ $i$ $f(x_1)$ $f(x_{N+1})$
$f (x) = x^{2}$ $f(x) = x^2$ $x_1 = -1$ $x_2=1$ . Algorytm zbiegałby się tutaj, nie znajdując swojego optymalnego.
Druga opcja polega na ocenie środka ciężkości simpleks: zatrzymaj, jeśli . Zakłada się, że jeśli najniższy punkt simpleksu i centroidu mają podobne wartości, simpleks jest wystarczająco mały, aby wywołać konwergencję. $|f(x_1) - f(x_c)| < \epsilon$

Czy to właściwy sposób sprawdzenia konwergencji? Czy istnieje ustalony sposób na sprawdzenie tego? Nie mogłem znaleźć żadnych źródeł na ten temat, ponieważ większość wyszukiwań skupia się na złożoności algorytmu.

optimization algorithms

— JAD
źródło

1. Nie jest dla mnie jasne, dlaczego porównujesz to, co dzieje się w z ; na pewno chcesz to porównać z tym, co dzieje się na . 2. Kontrole konwergencji są szczególnie trudnym obszarem w wielu procesach optymalizacji; potrzebujesz, aby funkcja niewiele się zmieniała, ale jeśli argumenty zmieniają się gwałtownie (nawet jeśli funkcja ledwo się zmienia), być może nie zbiegasz się, więc ludzie często używają kryteriów, które patrzą na oba. Istnieje również kwestia, czy używasz kryterium względnego, czy bezwzględnego (to też nie wystarczy - np. Test względny, gdy jesteś bardzo blisko 0, nie zostanie uruchomiony)

x_{N + 1}

$x_{N+1}$

x_{1}

$x_1$

x_{N}

$x_N$

— Glen_b

3

Najlepsze kryterium zatrzymania dla Nelder Mead jest przed rozpoczęciem.

— Mark L. Stone

Aby uniknąć nieporozumień, notacja wrt w komentarzu @ Glen_b ... Wierzę, że indeksy tutaj odnoszą się do wierzchołków simpleks, a nie do iteracji algorytmu. Tak więc pierwsze kryterium konwergencji zaproponowane w tym pytaniu porównuje najniższą i najwyższą wartość funkcji wierzchołków w przestrzeni parametrów wymiarowych ... nie jest to wyraźnie określone w pytaniu, ale w opisie algorytmu na powiązanej stronie Wikipedii ( oraz w oryginalnym papierze) uporządkuj wierzchołki od najniższej wartości funkcji do najwyższej.

N

$N$

N + 1

$N+1$

— Nate Pope

@NatePope To był mój zamiar tak, dodam wyjaśnienie do pytania. \

— JAD

6

Opis tego „algorytmu zjazdowego simpleksu” w oryginalnych wersjach przepisów numerycznych jest szczególnie przejrzysty i pomocny. Zacytuję zatem jego odpowiednie części. Oto tło:

W minimalizacji jednowymiarowej możliwe było ograniczenie minimum ... Niestety! W przestrzeni wielowymiarowej nie ma analogicznej procedury. ... Najlepsze, co możemy zrobić, to odgadnąć nasz algorytm; to jest wektor zmiennych niezależnych jako pierwszy punkt do wypróbowania. Algorytm powinien następnie zejść w dół przez niewyobrażalną złożoność topografii wymiarowej, aż napotka minimum (przynajmniej lokalne) minimum. $N$ $N$

Metodę simpleks zjazdową należy uruchomić nie tylko z jednym punktem, ale z punktami , określającymi początkowy simpleks. [Możesz wziąć te punkty za początkowy punkt początkowy wraz z] gdzie to wektory jednostkowe i gdzie jest stałą, którą zgadujesz charakterystycznej skali długości problemu. ... $N+1$ $P_0$
$\begin{matrix} (10.4.1) & P_{i} = P_{0} + λ e_{i} \end{matrix}$ $P_i = P_0 + \lambda e_i\tag{10.4.1}$ $e_i$ $N$ $\lambda$
Większość kroków po prostu [przesuwa] punkt simpleksu, w którym funkcja jest największa („najwyższy punkt”), przez przeciwległą powierzchnię simpleksu do niższego punktu. ...

Teraz pora na rozwiązanie problemu, zakończenie algorytmu. Zwróć uwagę na ogólność konta: autorzy zapewniają intuicyjną i przydatną poradę dotyczącą zakończenia dowolnego wielowymiarowego optymalizatora, a następnie szczegółowo pokazują, w jaki sposób ma on zastosowanie do tego konkretnego algorytmu. Pierwszy akapit odpowiada na postawione przed nami pytanie:

Kryteria zakończenia mogą być delikatne ... Zazwyczaj możemy zidentyfikować jeden „cykl” lub „krok” naszego wielowymiarowego algorytmu. Można wtedy zakończyć, gdy odległość wektora przesunięta w tym etapie jest ułamkowo mniejsza pod względem wielkości niż pewna tolerancja TOL. Alternatywnie, moglibyśmy wymagać, aby spadek wartości funkcji w etapie kończącym był ułamkowo mniejszy niż pewna tolerancja FTOL. ...

Zauważ dobrze, że którekolwiek z powyższych kryteriów może dać się zwieść pojedynczemu anormalnemu krokowi, który z tego czy innego powodu nigdzie nie dotarł. Dlatego często dobrym pomysłem jest ponowne uruchomienie wielowymiarowej procedury minimalizacji w punkcie, w którym twierdzi, że znalazła minimum. W przypadku tego ponownego uruchomienia należy ponownie zainicjować wszelkie pomocnicze wielkości wejściowe. Na przykład w metodzie simpleks zjazdowej należy ponownie zainicjować z wierzchołków simpleksu równaniem , przy czym jest jednym z wierzchołków deklarowanego minimum. $N$ $N+1$ $(10.4.1)$ $P_0$

Ponowne uruchomienie nigdy nie powinno być bardzo drogie; W końcu twój algorytm zbiegnął się do punktu restartu, a teraz uruchamiasz algorytm już tam.

[Strony 290–292.]

Kod towarzyszących tekst w Numerical Recipes wyjaśniono znaczenie „frakcjonowanej mniejszy”: różnica między wartościami i (albo wartości argumentu lub wartości funkcji) to „frakcjonowanej mniejsza” niż wartość progowa gdy $x$ $y$ $T\gt 0$

\begin{matrix} (1) & \frac{| x | - | y |}{f (x, y)} = 2 \frac{| x | - | y |}{| x | + | y |} < T \end{matrix}

$\frac{|x| - |y|}{f(x,y)} = 2\frac{|x|-|y|}{|x| + |y|} \lt T\tag{1}$

z . $f(x,y) = (|x|+|y|)/2$

Lewa strona jest czasem znana jako „względna różnica bezwzględna”. W niektórych polach jest wyrażany jako procent, gdzie nazywany jest „względnym błędem procentowym”. Zobacz artykuł w Wikipedii na temat względnych zmian i różnic, aby uzyskać więcej opcji i terminologii. $(1)$

Odniesienie

William H. Press i in. , Przepisy numeryczne: Sztuka informatyki naukowej. Cambridge University Press (1986). Odwiedź http://numerical.recipes/ najnowszych wydaniach.

— Whuber
źródło

1

Dziękujemy za wgląd w ponowne uruchomienie. Myślałem, że to po prostu uruchamia algorytm z różnych punktów początkowych, ale tak naprawdę wydaje się, że jest coś więcej.

— JAD

Nie myślałem wcześniej o możliwych znaczeniach „restartowania”. W obecnym kontekście mógłbym użyć terminu „polerowanie” dla „restartu”, ale może też nie jest to w porządku. Rodzaj „restartu” zalecany dla metody simpleks może być dla niej raczej szczególny.

— whuber

9

Nie jest to kompletna odpowiedź, ale za długa na komentarz i może postawić cię na właściwej drodze.

Temat ten jest krótko omówiony na stronie 171 „Kompaktowych metod numerycznych dla komputerów”, wydanie drugie, John C. Nash. I zdarza się, że jest to odwołanie cytowane dla procedury Neldera-Meada zaimplementowanej w optim()funkcji R. Cytując odpowiednią część:

Należy zatem odpowiedzieć na najostrzejsze pytanie dotyczące algorytmów minimalizacji: kiedy znaleziono minimum? Nelder i Mead sugerują „błąd standardowy” wartości funkcji: Gdzie
$t e s t = {[(\sum_{i = 1}^{n + 1} [S (b_{i}) - \bar{S}]^{2}) / n]}^{1 / 2}$ $\mathrm{test} = \left[ \left( \sum_{i=1}^{n+1}[S(b_i) - \bar{S}]^2 \right) / n \right]^{1/2}$ $\bar{S} = \sum_{i = 1}^{n + 1} S (b_{i}) / (n + 1) .$ $\bar{S} = \sum_{i=1}^{n+1} S(b_i)/(n+1).$

Będę przerywać, aby wyjaśnić, że Jest funkcją, która jest minimalizowana, są punktami które definiują wymiarowy simpleks; punkt o najwyższej wartości funkcji to a punkt o najniższej wartości funkcji to . Nash kontynuuje: $S(.)$ $b$ $n+1$ $n$ $b_H$ $b_L$

Przyjmuje się, że procedura jest zbieżna, gdy wartość testu spadnie poniżej ustalonej tolerancji. W zastosowaniach statystycznych, które zainteresowały Neldera i Meada, takie podejście jest uzasadnione. Jednak autor stwierdził, że to kryterium może powodować przedwczesne zakończenie procedury w przypadku problemów z dość płaskimi obszarami na powierzchni funkcji. W kontekście statystycznym można by zatrzymać, gdyby napotkano taki region, ale zakładając, że poszukiwane jest minimum, logiczne wydaje się stosowanie prostszego testu na równość między i , to znaczy test na równą wysokość wszystkich punktów w jednostronie. $S(b_L)$ $S(b_H)$

Szybkie spojrzenie na źródło optim()wskazuje, że wykorzystuje różnicę między najwyższą a najniższą wartością funkcji (punktów definiujących simpleks) do ustalenia zbieżności: if (VH <= VL + convtol || VL <= abstol) break;Gdzie VHjest wysoka wartość, a VLniska wartość. Jest to związane z zastrzeżeniem, że rzuciłem okiem na źródło i prawdopodobnie czegoś mi brakuje.

Teraz twoja opcja (1) wydaje się drugim podejściem zalecanym przez Nasha. Omawia również napotkany problem:

Wreszcie nadal możliwe jest zbieganie się w punkcie, który nie jest minimum. Jeśli na przykład wszystkie punkty simpleksu znajdują się w jednej płaszczyźnie (która jest linią w dwóch wymiarach), simpleks może poruszać się tylko w kierunkach w przestrzeni wymiarowej i może nie być w stanie przejść do minimum. O'Neill (1971), w implementacji FORTRAN pomysłów Neldera-Meada, testuje wartość funkcji po obu stronach przypuszczalnego minimum wzdłuż każdej z osi parametrów. Jeśli jakakolwiek wartość funkcji zostanie znaleziona poniżej aktualnego przypuszczalnego minimum, procedura zostanie ponownie uruchomiona. $(n+1)$ $(n-1)$ $n$

Oryginalne odniesienia, do których odnosi się Nash, to:

Nelder JA, Mead R. 1965. Prostokątna metoda minimalizacji funkcji. The Computer Journal 7: 308-313.

O'Neill R. 1971. Algorytm AS 47: Minimalizacja funkcji za pomocą procedury simpleks. Statystyka stosowana 20: 338–345.

— Nate Pope
źródło

3

Słomkowy człowiek: śledź tylko najniższy róg z regułą zatrzymania „cierpliwości” :

f_{min} (t) \equiv {min}_{all corners} f (X_{i}, t)

$f_{\text{min}}(t) \equiv \text{min}_{\text{all corners}} \ f(X_i, t)$

# stop when you run out of patience, no improvement for say 10 iterations in a row:
if t > tbest + patience:
    message = "iter %d: f %g >= fbest %g" ...
    return message, fbest, xbest

Monitorowanie wszystkich narożników jest zdecydowanie przydatne w sprawdzaniu rozsądnego skalowania współrzędnych, ograniczeń, początkowego jednostronnego NM. Czy śledzenie wszystkich zakrętów może poprawić kombinację $n+1$

problem: trudny teren, być może ze złym skalowaniem lub głupimi ograniczeniami
algorytm, równoważenie eksploracji i przenoszenia (oraz złożoność oprogramowania)
właściwa reguła zatrzymania

pozostaje do zobaczenia - mile widziane prawdziwe przypadki testowe.

( StopiterPoza tym prawdziwa klasa ma wiele warunków zatrzymania patience; najprostszym jest czas naścienny).

Zobacz także:
NLopt : wiele algorytmów, w tym Nelder-Mead, łatwe do porównania. Zobacz zwłaszcza uwagi na temat porównywania algorytmów
Downhill : cierpliwość się kończymin_improvement

— denis
źródło