Zoptymalizować nieznaną funkcję, którą można ocenić tylko?

Biorąc pod uwagę nieznaną funkcję , możemy ocenić jej wartość w dowolnym punkcie w jej dziedzinie, ale nie mamy jej wyrażenia. Innymi słowy, jest dla nas jak czarna skrzynka. $f:\mathbb R^d \to \mathbb R$ $f$

Jak nazywa się problem znalezienia minimalizatora ? Jakie są metody? $f$

Jak nazywa się problem znalezienia rozwiązania równania ? Jakie są metody? $f(x)=0$

W powyższych dwóch problemach dobrym pomysłem jest interpolacja lub dopasowanie do niektórych ocen f: przy użyciu funkcji o znanej formie i parametrze do ustalenia, a następnie zminimalizować lub znaleźć jego korzeń? $(x_i, f(x_i)), i=1, \dots, n$ $g_\theta$ $\theta$ $g_\theta$

Dziękuję i pozdrawiam!

optimization

— Tim
źródło

Czy potrafisz ocenić jego gradient w danym punkcie?

— chaohuang

@chaohuang: Istnieją dwa przypadki: możesz oceniać jego gradient w zależności od założeń.

— Tim

Jeśli gradient jest dostępny, zadania, o które pytasz, można wykonać za pomocą algorytmów opartych na gradiencie. Na przykład minimum lub przynajmniej lokalne minimum można obliczyć metodą najbardziej stromego spadku, a pierwiastki można znaleźć metodą Newtona.

— chaohuang

A jeśli gradient nie jest znany, istnieją metody metaheurystyczne , które są również nazywane metodami bez pochodnych lub czarnymi skrzynkami i zwykle w postaci optymalizacji stochastycznej.

— chaohuang

Czy wiesz, czy funkcja jest płynna (nawet jeśli nie możesz ocenić gradientu)? Czy wiesz, czy funkcja jest wypukła? Jeśli nie jest wypukły, czy wiesz, czy to przynajmniej ciągłość Lipschitza? Jeśli funkcja jest całkowicie ogólna, jest to beznadziejny problem.

— Brian Borchers,

Odpowiedzi:

Metody, których szukasz - tj. Które używają tylko oceny funkcji, ale nie pochodnych - są nazywane metodami optymalizacji bez pochodnych . Jest na nich obszerna literatura, a rozdział o takich metodach można znaleźć w większości książek na temat optymalizacji. Typowe podejścia obejmują

Przybliżenie gradientu różnicami skończonymi, jeśli można racjonalnie oczekiwać, że funkcja będzie gładka i ewentualnie wypukła;
Metody Monte Carlo, takie jak Symulowane Wyżarzanie;
Algorytmy genetyczne.

— Wolfgang Bangerth
źródło

Czy mogę po prostu dodać do tej listy „Modelowanie zastępcze”? Są one bardzo przydatne do optymalizacji czarnej skrzynki, zwłaszcza jeśli ocena funkcji jest kosztowna.

— OscarB

Tak, możesz :-) Z pewnością świetny dodatek.

— Wolfgang Bangerth,

Można również zastosować metodę Neldera-Meada, jeśli znane są dobre szacunki optymów.

— JM

Tak, możesz użyć Nelder-Mead, ale jest to straszny algorytm w porównaniu do większości innych.

— Wolfgang Bangerth,

@WolfgangBangerth: Twój komentarz do Nelder-Mead jest ważny tylko w wymiarze d> 2. W dwóch wymiarach jest to doskonała i bardzo trudna do pokonania metoda.

— Arnold Neumaier,

Myślę, że powinieneś zacząć od: Warsztatów GECCO na temat analizy porównawczej optymalizacji czarnych skrzynek Real-Parameter (BBOB 2016) http://numbbo.github.io/workshops/index.html

Znajdziesz wiele różnych algorytmów, które były używane w poprzednich konkursach i które zostały porównane na wspólnej podstawie. Jeśli zaczniesz gdzie indziej, wkrótce utopisz się w setkach dokumentów, które twierdzą, że ich metody i algorytmy działają lepiej niż inne, z niewielkimi faktycznymi dowodami na te twierdzenia.

Do niedawna był to, szczerze mówiąc, haniebny stan rzeczy i wszelka władza dla INRIA, GECCO i wielu innych za wysiłek włożony w ustanowienie ram dla racjonalnych porównań.

— Lysistrata
źródło

-1

Dodam tylko, że jednym z kluczy jest możliwość skalowania metody optymalizacji na procesorach wielordzeniowych . Jeśli możesz wykonać kilka ocen funkcji jednocześnie, daje to przyspieszenie równe liczbie zaangażowanych rdzeni. Porównaj to z użyciem nieco dokładniejszego modelu reakcji, który sprawia, że jesteś o 10% bardziej wydajny.

Polecam przejrzeć ten kod , może być przydatny dla osób mających dostęp do wielu rdzeni. Matematyka stojąca za tym jest opisana w tym artykule .

— Paweł
źródło

Ta odpowiedź jest zbyt krótka, aby była użyteczna (i pozostaje użyteczna, ponieważ linki mogą zniknąć w dowolnym momencie). Proszę również wspomnieć, że jesteś autorem tego oprogramowania .

— Christian Clason