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.

  • 1
    $\begingroup$ since it's a 1d function, you can use golden section search, which finds the max of a unimodal function without derivatives. $\endgroup$ Feb 3 '15 at 4:25
  • $\begingroup$ Thanks for the pointer to golden section search. I previously tried a similar scheme but with equidistant spacing & occasional bisection. But using the golden ratio is a lot more elegant. However, I think I'll go with the surrogate model approach. $\endgroup$ Feb 3 '15 at 12:54

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.


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.