Algorithm for finding the minimum point of a function value

Question

I would like to find the smallest function value with the least number of tests. The function f(x) must have a point with a minimum value. Given input x , I can calculate f(x) , but not in the other direction. I don't have an explicit function expression, so this is a black box.

I would like to find an input x that minimizes f(x) , with the least number of tests (one test is when I select a specific x and connect it to get the output). Are there any algorithms to achieve this?

The result does not have to be an absolute minimum, as it is obtained from a real problem. But this should be less than most values.

If a function is bounded by a convex, is there a better way to achieve it?

Thanks!

Answer 1

Assuming that the function is convex and that there is a derivative of f(x) , for all points => there is only one minimum. The reason I emphasize the restriction of the derivative is that in the case where the function looks like two convex functions one next to the other at the intersection point, the derivative does not 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 directions). You can see a visualization of this here . With that in mind, you can do a simple binary search in your domain to find a point k that satisfies f'(ke) * f'(k+e) < 0 , the less you choose e , the better the accuracy of the result. When performing the search, let [a,b] be an interval, and k=(a+b)/2 you must select left if f'(k)*f'(a) < 0 and otherwise otherwise.

Having f(x) , f'(x) = (f(x+e)-f(x))/e , you again reduce e , better the accuracy of the derivative.

Answer 2

If the function is random, I think that it is not possible to quickly find the minimum, because if f (x) can be anything (black box), then there is no guarantee that this function is a continuous function.

If the function is convex, it can be approximated by a parabola.

If the function is a real parabolic form, you can use 6 random points and calculate its values. Each parabola can be represented by 6 points, so you can calculate its function, and then calculate its minimum by derivation. This is only aproctimatin, but you can prepare the ab front derivation function (as a function of 6 variables), so you only need 7 stamps to calculate it (depends on how complicated f (x) is), but I think this is one of the fastest way. But then again, this is just a good example of a minimum.