Znalezienie globalnego minimum płynnej, ograniczonej, niewypukłej funkcji 2D, która jest kosztowna w ocenie

Mam ograniczoną niewypukłą funkcję 2-D, którą chciałbym znaleźć minimum. Funkcja jest dość płynna. Ocena jest kosztowna. Dopuszczalny błąd wynosi około 3% domeny funkcji w każdej osi.

Próbowałem uruchomić implementację algorytmu DIRECT w bibliotece NLOPT, ale nie dało to znacznej poprawy w porównaniu z wyszukiwaniem brutalnej siły pod względem ilości ocen funkcji potrzebnych do wymaganej dokładności i były pewne odchylenia.

Jakie inne globalne rozwiązania optymalizacyjne powinienem rozważyć?

Chciałbym zasugerować nieco inne podejście w porównaniu do innych odpowiedzi, chociaż @barron pośrednio omawiał to samo.

Zamiast bezpośrednio optymalizować swoją funkcję, tj. Oceniając ją w szeregu punktów punktów, które (miejmy nadzieję) są zbieżne z (lokalnym) optimum, możesz skorzystać z koncepcji modelowania zastępczego , która jest bardzo dobrze nadaje się do problemów opisywanego typu (wysoki koszt, gładki, ograniczony, mało wymiarowy, tj. mniej niż 20 niewiadomych).$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_k$$\textit{surrogate modelling}$

Konkretnie, modelowanie zastępcza działa poprzez utworzenie funkcji modelu swojej prawdziwej funkcji f ∈ R d → R . Kluczem jest to, że chociaż c oczywiście nie doskonale reprezentuje f , jest o wiele tańszy do oceny.$c \in \mathbb{R}^d \rightarrow \mathbb{R}$$f \in \mathbb{R}^d \rightarrow \mathbb{R}$$c$$f$

Typowy proces optymalizacji wyglądałby następująco:

1. Oszacuj na zbiorze j początkowych punktów x 1 , x 2 , … , x j . Należy pamiętać, że instrumenty pochodne nie są potrzebne. Zauważ również, że punkty te powinny być rozmieszczone równomiernie w przestrzeni wyszukiwania, np. Przez Latin Hypercube Sampling lub podobny projekt wypełniania przestrzeni.$f$$j$$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_j$
2. Na podstawie tego oryginalnego zestawu danych utwórz funkcję modelu . Możesz użyć weryfikacji krzyżowej, aby sprawdzić swój model (tj. Użyć tylko podzestawu oryginalnych punktów j, aby utworzyć c , a następnie użyć pozostałej części zestawu danych, aby sprawdzić, jak dobrze c przewiduje te wartości)$c$$j$$c$$c$
3. Użyj kryterium, takiego jak kryterium oczekiwanej poprawy (EI), aby dowiedzieć się, gdzie „wypełnić” więcej próbek, aby zwiększyć dokładność poprzez pobranie próbki f . Jest to właściwie znacznie lepiej zbadane teoretycznie, niż mogłoby się wydawać, a kryterium EI jest bardzo dobrze zbadane. Kryterium EI nie jest również chciwym kryterium, więc oboje uzyskuje się dobrą ogólną poprawę dokładności modelu, przy jednoczesnym priorytetowym traktowaniu dokładności w pobliżu potencjalnych optymów.$c$$f$
4. Jeśli twój model nie jest wystarczająco dokładny, powtórz krok 3, w przeciwnym razie użyj ulubionej procedury optymalizacji, aby znaleźć optymalną wartość , która będzie bardzo tania w ocenie (abyś mógł zastosować dowolną procedurę, nawet wymagającą pochodnych, lub po prostu ocenić funkcję w drobnej siatce).$c$

Zasadniczo to właśnie oznacza EGO, Efficient Global Optimization, jak sugerował @barron. Chciałbym podkreślić, że dla twojej aplikacji wydaje się to idealnie odpowiednie - otrzymujesz zaskakująco dokładny model oparty na stosunkowo niewielu ocenach , a następnie możesz użyć dowolnego algorytmu optymalizacji, który chcesz. Często interesujące jest również to, że możesz teraz ocenić c na siatce i narysować ją, uzyskując w ten sposób wgląd w ogólny wygląd f . Innym interesującym punktem jest to, że większość zastępczych technik modelowania zapewnia również szacunki błędów statystycznych, umożliwiając w ten sposób oszacowanie niepewności.$f$$c$$f$

Jak skonstruować jest oczywiście pytaniem otwartym, ale często stosuje się modele Kriginga lub tak zwane modele mapowania przestrzeni.$c$

Oczywiście jest to dość sporo pracy z kodowaniem, ale wiele innych osób wykonało bardzo dobre wdrożenia. W Matlab znam tylko programowy zestaw narzędzi DACE. DACE jest bezpłatny. TOMLAB może również oferować pakiet Matlab, ale kosztuje, ale uważam, że działa również w C ++ i ma znacznie więcej możliwości niż kiedykolwiek będzie miał DACE. (Uwaga: jestem jednym z twórców nowej wersji DACE, która wkrótce zostanie wydana, która zaoferuje dodatkowe wsparcie dla EGO.)

Mam nadzieję, że ten ogólny przegląd pomógł ci, zadawaj pytania, czy są pewne kwestie, które można wyjaśnić, lub rzeczy, które mi pominęły, lub jeśli chcesz uzyskać więcej materiałów na ten temat.

Widzieć

LM Rios i NV Sahinidis, Optymalizacja bez instrumentów pochodnych: przegląd algorytmów i porównanie implementacji oprogramowania

za bardzo przydatne ostatnie porównanie solverów.

DOI: 10.1007 / s10898-012-9951-y

Aby zapewnić płynne działanie, metoda wydajnej globalnej optymalizacji powinna działać całkiem dobrze i być znacznie bardziej wydajna niż DIRECT. Implementacje są dostępne w TOMLAB (sam nie korzystałem z niego) i DAKOTA (z którym miałem pewien sukces).

Ponieważ funkcja jest płynna, metoda Newtona będzie niezwykle wydajną metodą znajdowania minimum. Ponieważ funkcja nie jest wypukła, będziesz musiał zastosować zwykłe sztuczki, aby metoda Newtona zbiegła się (modyfikacja Levenberga-Marquardta, wyszukiwanie linii lub region zaufania w celu globalizacji). Jeśli nie możesz uzyskać pochodnych funkcji, spróbuj ją obliczyć za pomocą różnic skończonych lub zaktualizować BFGS. Jeśli podejrzewasz, że problem ma więcej niż jedno lokalne minimum, wystarczy po prostu uruchomić metodę Newtona z zestawu losowo lub niezbyt losowo wybranych punktów i sprawdzić, gdzie się zbiegają.

Ponieważ twoje oceny są drogie, musisz skorzystać z równoległego wykonywania ocen funkcji różnych.

Polecam zajrzeć do tego kodu . Opisana tutaj matematyka .