Optymalizacja matematyczna funkcji głośnej

Niech będzie funkcją, która jest dość ładna (np. Ciągła, różniczkowalna, niezbyt wiele lokalnych maksimów, może wklęsła itp.). Chcę znaleźć maksima : wartość która sprawia, że tak duże, jak to możliwe. $f:\mathbb{R}^d \to \mathbb{R}$ $f$ $x \in \mathbb{R}^d$ $f(x)$

Gdybym miał procedurę oceny na dowolnym wybranym przez siebie danych wejściowych, mógłbym zastosować standardowe techniki optymalizacji matematycznej : wspinanie się na wzniesienie, opadanie gradientu (cóż, wznoszenie gradientu) itp. Jednak w mojej aplikacji nie mam sposób na dokładne oszacowanie . Zamiast tego mam sposób oszacowania wartości . $f$ $f(x)$ $f(x)$

W szczególności, biorąc pod uwagę dowolne i dowolne , mam wyrocznię, która wyświetli oszacowanie i której oczekiwany błąd wynosi w przybliżeniu . Czas działania tego wywołania wyroczni jest proporcjonalny do . (Jest realizowany przez rodzaj symulacji; dokładność symulacji wzrasta wraz z pierwiastkiem kwadratowym z liczby prób, i mogę wybrać liczbę prób do uruchomienia, więc mogę wybrać pożądaną dokładność.) To daje mi sposób, aby uzyskać oszacowanie jakiejkolwiek dokładności, jakiej pragnę, ale im dokładniejsze chcę oszacowanie, tym dłużej mi to zajmie. $x$ $\varepsilon$ $f(x)$ $\varepsilon$ $1/\varepsilon^2$

Biorąc pod uwagę tę głośną wyrocznię dla , czy są jakieś techniki obliczania maksimów tak skutecznie, jak to możliwe? (Lub, ściślej, znalezienie przybliżonych maksimów.) Czy istnieją warianty wspinaczki, zjazdu itp., Które działają w tym modelu? $f$ $f$

Oczywiście, mógłbym ustalić bardzo małą wartość i zastosować wspinanie się po zboczu lub zejście gradientowe za pomocą tej wyroczni, utrzymując tę samą wartość przez cały czas. Może to być jednak niepotrzebnie nieefektywne: możemy nie potrzebować tak dokładnych oszacowań na początku, podczas gdy dokładność pod koniec, gdy zaczynasz od rozwiązania, jest ważniejsza. Czy jest więc jakiś sposób, aby skorzystać z mojej możliwości dynamicznego kontrolowania dokładności moich oszacowań, aby usprawnić proces optymalizacji? Czy tego rodzaju problem był już badany? $\varepsilon$ $\varepsilon$

optimization approximation

— DW
źródło

Wydaje się, że bardzo problem z optymalizacją stawek uzasadnia własny kierunek studiów. A co z symulowanym wyżarzaniem? Czy możesz dostosować pomysły stamtąd - prawdopodobieństwa przejścia i harmonogram temperatur? Istnieje związek istnieje - jak postępować ze spadkiem temperatury, a w przypadku, gdy chcesz

spadać.

ϵ

$\epsilon$

— randomsurfer_123

Cybernetyczna chroniczność, ostatnio trafiła właśnie na ten przypadek w programie GA. zgodził się z rs powyżej, że symulowane wyżarzanie, w którym dokładność oceny funkcji z grubsza odpowiada spadkowi temperatury, powinna działać. Innym pomysłem jest wykonanie stałej liczby próbek w każdym punkcie i wzięcie średniej jako wartości szacunkowej. bardziej zaawansowana teoria może tylko powiedzieć, że nie możesz dostać czegoś za nic i że nie ma skrótu do ocen poprawiających optymalizację.

— vzn

$f(x,p)$ $f(x+\Delta x, p + \Delta p)$ $p$ $\Delta x$ $\Delta p$

Niektóre techniki stosowane w optymalizacji stochastycznej i solidnej optymalizacji mogą mieć zastosowanie.
$\frac{\partial f}{\partial x}\approx 0$ $\Delta x$ $\Delta p$
$\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$ $f(\tilde{x}, \tilde{p})$
$\Delta p$ $\Delta x$ $1/\epsilon^2$
Dany hałas w porównaniu do kompromisów w czasie wykonywania wyróżnia ten problem spośród lepiej zbadanych problemów. Problemy, w których hałas jest po prostu nieunikniony, są bardziej powszechne i lepiej badane.

— Thomas Klimpel
źródło

f (x, p)

$f(x,p)$

f^{*} (x + Δ x, Δ p)

$f^*(x+\Delta x,\Delta p)$

p

$p$

p = 0

$p=0$

f^{*}

$f^*$ ). Optymalizacja stochastyczna i solidna optymalizacja brzmią mniej więcej tak, jak tego szukałem, więc jest to bardzo pomocne. Dziękuję Ci.

— DW

p = 0

$p=0$

f (x, 0)

$f(x,0)$

f (x + Δ x, Δ p)

$f(x+\Delta x, \Delta p)$

Δ x

$\Delta x$

Δ p

$\Delta p$