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 f : wartość x ∈ R d, która sprawia, że f ( x ) jest 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 f ( x ) . Zamiast tego mam sposób oszacowania wartości f ( x ) .$f$$f(x)$$f(x)$

W szczególności, biorąc pod uwagę dowolne i dowolne ε , mam wyrocznię, która wyświetli oszacowanie f ( x ) i której oczekiwany błąd wynosi w przybliżeniu ε . Czas działania tego wywołania wyroczni jest proporcjonalny do 1 / ε 2 . (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 f 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$

$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.