Mathematische Optimierung einer verrauschten Funktion

Sei eine Funktion, die ziemlich nett ist (z. B. stetig, differenzierbar, nicht zu viele lokale Maxima, vielleicht konkav usw.). Ich möchte ein Maximum von f finden : einen Wert x ∈ R d , der f ( x ) so groß wie möglich macht.$f:\mathbb{R}^d \to \mathbb{R}$$f$$x \in \mathbb{R}^d$$f(x)$

Wenn ich ein Verfahren hätte, um bei einer Eingabe meiner Wahl genau zu bewerten , könnte ich mathematische Standardoptimierungstechniken verwenden: Bergsteigen, Gefälle (gut, Gefälle) usw. In meiner Anwendung habe ich jedoch keine Weg, um f ( x ) genau zu bewerten . Stattdessen habe ich eine Möglichkeit, den Wert von f ( x ) zu schätzen .$f$$f(x)$$f(x)$

Insbesondere habe ich bei jedem und jedem ε ein Orakel, das eine Schätzung von f ( x ) ausgibt und dessen erwarteter Fehler ungefähr ε beträgt . Die Laufzeit dieses Orakelaufrufs ist proportional zu 1 / ε 2 . (Es wird durch eine Art Simulation implementiert. Die Genauigkeit der Simulation steigt mit der Quadratwurzel der Anzahl der Versuche, und ich kann auswählen, wie viele Versuche ausgeführt werden sollen, damit ich die gewünschte Genauigkeit auswählen kann.) Dies gibt mir also eine Weg, um eine Schätzung der gewünschten Genauigkeit zu erhalten, aber je genauer die Schätzung sein soll, desto länger dauert es.$x$$\varepsilon$$f(x)$$\varepsilon$$1/\varepsilon^2$

Gibt es angesichts dieses lauten Orakels für Techniken, um ein Maximum von f so effizient wie möglich zu berechnen ? (Oder genauer gesagt, ein ungefähres Maximum finden.) Gibt es Varianten des Bergsteigens, des Gefälles usw., die in diesem Modell funktionieren?$f$$f$

Natürlich könnte ich mit diesem Orakel einen sehr kleinen Wert von festlegen und Bergsteigen oder Gefälle anwenden , wobei ich ε durchgehend beibehalten würde . Dies kann jedoch unnötig ineffizient sein: Wir benötigen möglicherweise keine so genaue Schätzung am Anfang, während die Genauigkeit am Ende, wenn Sie sich auf die Lösung konzentrieren, wichtiger ist. Gibt es also eine Möglichkeit, meine Fähigkeit zu nutzen, die Genauigkeit meiner Schätzung dynamisch zu steuern, um den Optimierungsprozess effizienter zu gestalten? Wurde diese Art von Problem schon einmal untersucht?$\varepsilon$$\varepsilon$

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

• Einige Techniken, die bei der stochastischen Optimierung und der robusten Optimierung verwendet werden, könnten anwendbar sein.
• $\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$
• Der gegebene Kompromiss zwischen Rauschen und Laufzeit unterscheidet dieses Problem von besser untersuchten Problemen. Probleme, bei denen der Lärm einfach unvermeidbar ist, sind häufiger und besser untersucht.