Algorithm to find the minimum value point of a function

Question

I would like to find the lowest value of a function with the least number of trials. The function f(x) must have a point with minimum value. Given input x, I can calculate f(x), but not the other direction. I don't have the explicit expression of the function, so it is a blackbox.

I would like to find the input x such that minimizes f(x), with the least number of trials (One trial is when I choose a specific x, and plug it in to get the output). Are there any algorithms to achieve that?

The result doesn't need to be the absolute minimum, since it is derived from a real problem. But it should be less than most of the values.

If the function is constrained to be convex, is there a better way to achieve that?

Thanks!

Answer 1

Assuming that the function is convex and the derivative of f(x) exist for all points => there is only one minima. The reason I am stressing the derivative constrain is that in the case when the function looks like two convex functions one next to another at the point of intersection the derivative doesn't exist, but the function is still convex and there are two local minima.

The derivative will have opposite signs to the left and to the right of the minima (the slope changes the directions) You can see a visualization of that here. Having this in mind you can do a simple binary search on your domain to find a point k that satisfies f'(k-e) * f'(k+e) < 0 the smaller you pick e, better the precision of the result. When doing the search let [a,b] be the interval and k=(a+b)/2 you would select left if f'(k)*f'(a) < 0 and right otherwise.

Having f(x), f'(x) = (f(x+e)-f(x))/e, again smaller you pick e, better the precision of the derivative.