Jak wybrać odpowiedni algorytm optymalizacji?

Muszę znaleźć minimum funkcji. Czytając dokumenty na stronie http://docs.scipy.org/doc/scipy/reference/optimize.html Widzę, że istnieje kilka algorytmów, które robią to samo, tzn. Znajdują minimum. Skąd mam wiedzieć, który wybrać?

niektóre z wymienionych algorytmów

• Zminimalizuj funkcję za pomocą algorytmu downhill simplex.
• Zminimalizuj funkcję za pomocą algorytmu BFGS.
• Zminimalizuj funkcję za pomocą nieliniowego algorytmu gradientu sprzężonego.
• Zminimalizuj funkcję f za pomocą metody Newton-CG.
• Zminimalizuj funkcję za pomocą zmodyfikowanej metody Powella.

Moja funkcja jest liniowa. wymiarowość wynosi około 232750 (tyle różnych gradientów muszę obliczyć za każdym razem), obliczenie gradientu i kosztu zajmuje około 2 minut, więc nie jest tanie. Nie sądzę, że mam ograniczenia. jest deterministyczny i ciągły.

Na podstawie tego, co powiedziałeś: Zakładam, że musisz zoptymalizować pod kątem 50 zmiennych; Zakładam również, że masz sytuację, że znalezienie analitycznych pochodnych jest bardzo drogie (nie mówiąc już o wydobyciu liczb) i że twoja optymalizacja nie jest ograniczona.

Pozwólcie, że podkreślę, że jesteście trochę nieszczęśliwie, ponieważ pomiędzy 25-30 a 100 zmiennymi jest to trochę strefa zmierzchu, jeśli chodzi o wybór między procedurami optymalizacji na dużą lub małą skalę. Powiedziawszy to, nic nie jest stracone.

Biorąc pod uwagę, że nawet pochodne pierwszego rzędu są drogie, aby uzyskać tego rodzaju, zabija ideę metody Newtona. Możesz mieć jednak trochę szczęścia z Quasi-Newtonem (BFGS), jeśli twój Hesjan jest lekko przekątny, jak na początek. CG jest zwykle nieco wolniejsze niż BFGS, więc prawdopodobnie nie poprawi to zbyt wiele; użyj go, jeśli problem stanowi także pamięć (lub w takim przypadku wybierz L-BFGS). Dodatkowo, biorąc pod uwagę, jak wolno ocenia się twoją funkcję, prosty najbardziej stromy algorytm zejścia / wyszukiwania linii byłby kręto wolny; to samo dzieje się z symulowanym wyżarzaniem i innymi losowymi wariantami wyszukiwania (zakładam, że nie masz dostępu do konsoli HMC i całego tego jazzu).

Tak więc, gdy potrzebujesz najlepszego zwrotu pieniędzy, jeśli chodzi o ocenę pojedynczej funkcji: Idź z metodą Powella i przetestuj COBYLA; mimo że jest ograniczonym algorytmem optymalizacji, ponieważ wewnętrznie liniowo aproksymuje gradient funkcji w celu przyspieszenia rzeczy, będzie w stanie skorzystać z liniowości funkcji. Również zdecydowanie spróbować NLopt dla Pythona . Mają wiele optymalizatorów bez gradientu; spróbuj UOBYQA; to także pomysł Powella (Unconstrained Optimization BY Quadratic Approximations).

Bardzo krótko: Algorytmy N-CG zależą od obliczenia Hesji, a twój Hesjan wydaje się bardzo drogi do obliczenia. NLCG i BFGS nie wymagają tego, chociaż mogą próbować go obliczyć raz w pierwszym kroku.

Celowo pominąłem algorytm simpleks, ponieważ jest to zupełnie inna bestia; nie ma nic wspólnego z gradientami jako takimi. Spróbuj, ale tak naprawdę nie mogę tego komentować; to naprawdę zależy od natury twojego problemu.

Pierwsze dobre odniesienie do optymalizacji numerycznej Książka CTKelly Iterative Methods for Optimization zaprowadzi cię dość daleko, całkiem nieźle.

Może powinieneś zdobyć książkę wprowadzającą na temat optymalizacji numerycznej. Będziesz musiał wziąć pod uwagę swoją funkcję, aby zdecydować się na algorytm.

Wśród wspomnianych algorytmów istotne różnice dotyczą tego, czy potrzebny jest jakobian czy hesian, czy tylko sama funkcja.

Biorąc pod uwagę, że jest to strona pytań i odpowiedzi statystycznych, a zatem dotyczy losowych zmiennych: upewnij się, że twoja funkcja jest deterministyczna, można ją ocenić w sposób zapewniający ciągłe wyniki w przestrzeni wyszukiwania.