CODEWITHSUNDEEP
algorithm
Jarvis Du
Jarvis Du

Reputation: 379

Algorithm to find the minimum value point of a function

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!

Upvotes: 7

Views: 7064

Answers (2)

Alexandru Barbarosie
Alexandru Barbarosie

Reputation: 2992

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.

Upvotes: 8

Marko Zadravec
Marko Zadravec

Reputation: 8730

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

If function is convex it can be approximated with parabola.

If function is realy parabolic shape, you could tabe 6 random points and calculate its values. Every parabola could be represented by 6 points so you could calcolated its function and then calculate its minimum by derivation. This is only aproctimatin but you could prepare function of derivation ab front ( as function of 6 variables ) so you will need only 7 staps to calculate it ( depends on how complex is f(x) ) but I thing this is one of the fastest way. But again this is only a good gues of the minimum.

Upvotes: -1

Related Questions