Optimización matemática en una función ruidosa.

Sea una función bastante agradable (p. Ej., Continua, diferenciable, no demasiados máximos locales, tal vez cóncavos, etc.). Quiero encontrar un máximo de f : un valor x ∈ R d que haga que f ( x ) sea lo más grande posible.$f:\mathbb{R}^d \to \mathbb{R}$$f$$x \in \mathbb{R}^d$$f(x)$

Si tuviera un procedimiento para evaluar precisión en cualquier entrada de mi elección, podría usar técnicas de optimización matemática estándar : escalada, descenso en gradiente (bueno, ascenso en gradiente), etc. Sin embargo, en mi aplicación no tengo un manera de evaluar f ( x ) exactamente. En cambio, tengo una manera de estimar el valor de f ( x ) .$f$$f(x)$$f(x)$

En particular, dado cualquier cualquier ε , tengo un oráculo que generará una estimación de f ( x ) , y cuyo error esperado es aproximadamente ε . El tiempo de ejecución de esta invocación de oráculo es proporcional a 1 / ε 2 . (Se implementa mediante un tipo de simulación; la precisión de la simulación aumenta con la raíz cuadrada del número de pruebas, y puedo elegir cuántas pruebas ejecutar, para poder elegir la precisión deseada). Entonces esto me da una es una forma de obtener una estimación de la precisión que deseo, pero cuanto más precisa quiera que sea, más tiempo me llevará.$x$$\varepsilon$$f(x)$$\varepsilon$$1/\varepsilon^2$

Dado este ruidoso oráculo para , ¿hay alguna técnica para calcular un máximo de f de la manera más eficiente posible? (O, más precisamente, encontrar un máximo aproximado). ¿Existen variantes de escalada, descenso en pendiente, etc., que funcionen dentro de este modelo?$f$$f$

Por supuesto, podría fijar un valor muy pequeño de y aplicar el ascenso de pendientes o el descenso de pendientes con este oráculo, manteniendo el mismo ε en todo momento. Sin embargo, esto podría ser innecesariamente ineficiente: es posible que no necesitemos una estimación tan precisa cerca del comienzo, mientras que la precisión cerca del final cuando se está enfocando en la solución es más importante. Entonces, ¿hay alguna forma de aprovechar mi capacidad para controlar la precisión de mi estimación dinámicamente, para hacer que el proceso de optimización sea más eficiente? ¿Se ha estudiado este tipo de problema antes?$\varepsilon$$\varepsilon$

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

• Algunas técnicas utilizadas en la optimización estocástica y la optimización robusta pueden ser aplicables.
• $\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$
• El ruido dado contra el tiempo de ejecución es lo que distingue este problema de los problemas mejor estudiados. Los problemas en los que el ruido es inevitable son más comunes y mejor estudiados.