Finding the minimum of a convex function with noisy evaluation

Question

I want to find the argument of a function for which it is minimal. The function is expected to be convex but I cannot evaluate it exactly so I have to deal with the fact that there's noise on top. The noise is purely statistical and I roughly know its magnitude. Essentially, I run a Monte Carlo simulation for each evaluation of the function, so I can even control the error.

I don't need to know the minimum with too much precision. The higher the value of the function, the larger the yield of the simulation.

Thus my requirements are:

• really costly function evaluation
• 1D function
• no derivative available
• convexity up to statistical errors of know magnitude

Also, it's rather important that the whole procedure is not terribly complicated. I'm aware of this thread:

Finding a global minimum of a smooth, bounded, non-convex 2D function that is costly to evaluate

but that's just a little too much. I need something simple, yet reliable. I tried a simple bisection scheme but that really didn't handle the noise too well.

Answer 1

A standard approach to these kinds of problems is to to evaluate the objective function at several points covering a reasonable range and fit a simple (e.g. a quadratic model) to the points, and then minimize this "response surface." You can repeat the process by fitting a new response surface using points near the minimum of the first fitted model. Response surface modeling or surrogate modeling was discussed in the answers to the earlier question you mentioned- it really is the simplest approach to such problems.

If your Monte Carlo simulations produce not just a function value but also an approximate subgradient, then there has been some research into methods that use inexact function values and subgradients. However, these kinds of approaches typically require a lot of function evaluations.