Minimization of function with random error

Question

I'm aware of techniques to find the minimum of a function $f(x)$ by taking iterative samples, such as Newton's Method.

Suppose, however, that what I can actually observe is $g(x) = f(x) + E$, where $E$ is a random variable of some unknown distribution. Assuming I can measure samples of $g(x)$ at arbitrary $x$, is there a known technique for estimating $x_m$ such that $f(x_m)$ is the minimum?

If this is not possible in the general case, is it possible if I know the distribution of $E$?

One thought I've considered is just using a standard minimization technique, taking multiple samples at each $x$ and computing the mean of $g_i(x)$ to estimate $f(x)$, but I'm wondering if there is a more efficient way to tackle this.

Answer 1

In these situations, "response surface models" are often used. The idea is to use regression techniques to fit a model (often a simple quadratic model is used) to the noisy function values and then minimize over the fitted response surface. There are many books and survey papers on this topic.

There has also been research on adapting conventional optimization methods to situations in which inaccurate function values or gradients are available. These methods typically require that the errors in the function values or gradients be bounded, and thus aren't likely to be useful to you.