Testowanie numerycznych metod optymalizacji: Rosenbrock vs. rzeczywiste funkcje testowe

15

Wydaje się, że istnieją dwa główne rodzaje funkcji testowych dla optymalizatorów bez pochodnych:

  • jednowierszowe, takie jak funkcja Rosenbrock ff., z punktami początkowymi
  • zestawy rzeczywistych punktów danych, z interpolatorem

Czy można porównać powiedzmy 10d Rosenbrock z prawdziwymi problemami z 10d?
Można to porównać na różne sposoby: opisać strukturę minimów lokalnych
lub uruchomić ABC optymalizatorów na Rosenbrock i kilka rzeczywistych problemów;
ale oba wydają się trudne.

(Może teoretycy i eksperymentatorzy to tylko dwie zupełnie różne kultury, więc proszę o chimerę?)

Zobacz też:


(Dodano we wrześniu 2014):
Poniższy wykres porównuje 3 algorytmy DFO na 14 funkcjach testowych w 8d z 10 losowych punktów początkowych: BOBYQA PRAXIS SBPLX z NLOpt
14 N-wymiarowych funkcji testowych, Python pod gist.github z tego Matlaba autorstwa A. Hedar × 10 jednorodno-losowych punktów początkowych w obwiedni każdej funkcji.×
×

Na przykład w Ackley górny wiersz pokazuje, że SBPLX jest najlepszy, a PRAXIS okropny; na Schwefel, prawy dolny panel pokazuje SBPLX znajdujący minimum w 5. losowym punkcie początkowym.

Ogólnie BOBYQA jest najlepszy na 1, PRAXIS na 5, a SBPLX (~ Nelder-Mead z ponownym uruchomieniem) na 7 z 13 funkcji testowych, z Powersum tossup. YMMV! W szczególności Johnson mówi: „Odradzałbym nieużywanie wartości funkcji (ftol) lub tolerancji parametrów (xtol) w optymalizacji globalnej”.

Wniosek: nie wkładaj wszystkich pieniędzy na jednego konia ani na jedną funkcję testową.

wprowadź opis zdjęcia tutaj

denis
źródło

Odpowiedzi:

13

Proste funkcje, takie jak Rosenbrocka, są używane do debugowania i wstępnego testowania nowo napisanych algorytmów: są szybkie w implementacji i wykonywaniu, a metoda, która nie jest w stanie dobrze rozwiązać standardowych problemów, raczej nie będzie dobrze działać na rzeczywistych problemach.

Aby zapoznać się z ostatnim dokładnym porównaniem metod wolnych od pochodnych dla drogich funkcji, zobacz Optymalizacja bez pochodnych: przegląd algorytmów i porównanie implementacji oprogramowania . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Journal of Global Optimization, 2012. (Zobacz także towarzyszącą stronę internetową: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
źródło
Profesorze Neumaier, czy mógłby Pan wskazać na pewne rzeczywiste problemy, dowody na to, że „metoda, która nie jest w stanie dobrze rozwiązać standardowych problemów, raczej nie działa dobrze na rzeczywiste problemy”? Zdaję sobie sprawę, że to nie jest łatwe. (Byłbym zainteresowany twoimi komentarzami do Hookera.) Ponadto, szybkie spojrzenie na modele c z twojego linku pokazuje, że princetonlibgloballib wymaga AMPL, a wszystkie source_convexmodels * .c mają brakujące „;” po fscanf () - banalny, ale
denis
@Denis: Problemy takie jak Rosenbrock wynikają z wczesnych dni automatycznej optymalizacji, w której ludzie wyodrębnili typowe trudności w prostych reprezentatywnych przykładach, które można zbadać bez złożoności numerycznej problemów z życia wziętych. Zatem nie są to tak naprawdę sztuczne, ale uproszczone modele prawdziwych trudności. Na przykład Rosenbrock ilustruje połączony efekt silnej nieliniowości i łagodnego złego stanu.
Arnold Neumaier,
Witryna AMPL ampl.com oferuje bezpłatną wersję studencką dla AMPL.
Arnold Neumaier,
7

Zaletą syntetycznych przypadków testowych, takich jak funkcja Rosenbrock, jest to, że istnieje istniejąca literatura do porównania, a społeczność ma poczucie, jak dobre metody zachowują się na takich przypadkach. Gdyby wszyscy używali własnych testów, o wiele trudniej byłoby dojść do konsensusu, które metody działają, a które nie.

Wolfgang Bangerth
źródło
1

(Mam nadzieję, że nie mam nic przeciwko temu, aby zająć się końcem tej dyskusji. Jestem tu nowy, więc proszę daj mi znać, jeśli popełniłem naruszenie!)

Funkcje testowe dla algorytmów ewolucyjnych są teraz znacznie bardziej skomplikowane niż były nawet 2 lub 3 lata temu, co widać w zestawach używanych w konkursach na konferencjach takich jak (bardzo) Kongres na temat obliczeń ewolucyjnych 2015. Widzieć:

http://www.cec2015.org/

Te zestawy testów zawierają teraz funkcje z kilkoma nieliniowymi interakcjami między zmiennymi. Liczba zmiennych może wynosić nawet 1000, i przypuszczam, że może wzrosnąć w najbliższej przyszłości.

Kolejną bardzo niedawną innowacją jest „Konkurs optymalizacji czarnej skrzynki”. Zobacz: http://bbcomp.ini.rub.de/

Algorytm może zapytać o wartość f (x) dla punktu x, ale nie uzyskuje informacji o gradiencie, w szczególności nie może przyjmować żadnych założeń dotyczących formy analitycznej funkcji celu.

W pewnym sensie może to być bliższe temu, co określiłeś jako „prawdziwy problem”, ale w zorganizowanym, obiektywnym otoczeniu.

Lysistrata
źródło
1) „bez sprzeciwu”: wręcz przeciwnie, twoje dobre linki są mile widziane! 2) jakieś dobre działki? Metody i problemy są fraktalizujące, więc coraz trudniej jest każdemu znaleźć problem podobny do ich. W szczególności, czy znasz metody prognozowania szeregów czasowych ?
denis
Funkcje celu w konkursie CEC 2015 na temat dynamicznej optymalizacji wielu celów można znaleźć na stronie: sites.google.com/site/cec2015dmoocomp/competition-process/... W przypadku innych konkursów przejdź do strony cec2015.org i kliknij konkursy, a następnie kliknij na przyjętych konkursach. Każdy ma swoje własne funkcje. Artykuły na niektórych z nich mają piękne wykresy (dla przypadków 2D). Konkursy konferencyjne GECCO można znaleźć na stronie: sigevo.org/gecco-2015/competitions.html#bbc Wyniki będą dostępne po 15 lipca
Lysistrata
0

Możesz mieć to, co najlepsze z obu światów. NIST ma szereg problemów związanych z minimalizatorami, takich jak dopasowanie do wielomianu 10-go stopnia , z oczekiwanymi wynikami i niepewnościami. Oczywiście udowodnienie, że wartości te są najlepszym rozwiązaniem, lub istnienie i właściwości innych minimów lokalnych jest trudniejsze niż na kontrolowanym wyrażeniu matematycznym.

Davidmh
źródło
Cóż, problemy NIST są niewielkie (2 3 1 1 11 7 6 6 6 6 6 parametrów). Czy istnieją zestawy testowe, które są zarówno „rzeczywiste”, jak i odtwarzalne dla dowolnego rogu „rzeczywistego”? Por. Zapytanie o Simulation-Based Optimization Problems
Denis