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ϵ x i i f ( x 1 ) f ( x N + 1 ) 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ę.
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.
Odpowiedzi:
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:
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:
[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 gdyx y T>0
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.
źródło
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ęść: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 bH bL
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;
GdzieVH
jest wysoka wartość, aVL
niska 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:
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.
źródło
Słomkowy człowiek: śledź tylko najniższy róg z regułą zatrzymania „cierpliwości” :
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
pozostaje do zobaczenia - mile widziane prawdziwe przypadki testowe.
(
Stopiter
Poza tym prawdziwa klasa ma wiele warunków zatrzymaniapatience
; 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ńczy
min_improvement
źródło