1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Did some preliminary reading on RSM. Is the basic idea that the samples are fit to a model, then we minimize based on the model function, taking additional samples (based on the iteration steps chosen from the model) and use those samples to steadily refine the model? I could see this working well for the application I have in mind, as the the function I'm optimizing should be roughly quadratic in the region I'm sampling. $\endgroup$
    – Dan Bryant
    Aug 1, 2015 at 18:24
  • $\begingroup$ Yes, iteratively refining the model around the minimum of the current model is a common approach. $\endgroup$ Aug 1, 2015 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.