Finding a minimum of a noisy function

Question

I have a certain function that calculates numerically, for every $x \in [0,10]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$ for e.g. 10000 values of $x$ in the range $[0,3]$ and return the $x$ for which $y$ is smallest. I am looking for fastest solutions.

I know that the general shape of the function is like the following plot:

I.e, it is like a function with a single minimum point, but with some added random noise of bounded size. Without the noise, I could easily find the minimum point using gradient methods, but with noise gradients seem useless. What other search algorithm can I use here?

NOTE: Naturally the approximation quality can depend on the noise size, for example, in the above plot, any answer between $\approx 0.3$ and $\approx 0.7$ would be considered good enough.

Answer 1

Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement.

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.

• Differential evolution
• Particle Swarm
• Evolutionary algorithms

There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize.

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia (Computational optimization techniques section).