CODEWITHSUNDEEP
c++algorithm
Pavel P
Pavel P

Reputation: 16843

finding maximum of a function with least probes taken

I have some code, a function basically, that returns a value. This function takes long time to run. Function takes a double as a parameter:

double estimate(double factor);

My goal is to find such parameter factor at which this estimate function returns maximum value. I can simply brute force and iterate different factor inputs and get what I need, but the function takes long time to run, so I'd like to minimize amount of "probes" that I take (e.g. call the estimate function as least as possible). Usually, maximum is returned for factor values between 0.5 and 3.5. If I graph returned values, I get something that looks like a bell curve. What's the most efficient approach to partition possible inputs to that I could discover maximum faster?

Upvotes: 0

Views: 101

Answers (2)

MSalters
MSalters

Reputation: 179799

The previous answer suggested a 2 point approach. This is a good idea for functions that are approximately lines, because lines are defined by 2 parameters: y=ax+b.

However, the actual bell-shaped curve is more like a parabola, which is defined by ax²+bx+c (so 3 parameters). You therefore should take 3 points {x1,x2,x3} and solve for {a,b,c}. This will give you an estimate for the xtop at -b/2a. (The linked answer uses the name x0 here).

You'll need to iteratively approximate the actual top if the function isn't a real parabola, but this process converges really fast. The easiest solution is to take the original triplet x1,x2,x3, add xtop and remove the xn value which is furthest away from xtop. The advantage of this is that you can reuse 2 of the old f(x) values. This reuse helps a lot with the stated goal of "mininal samples".

Upvotes: 2

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

If your function indeed has a bell shaped curve then you can use binary search as follows:

Choose an initial x1 (say x1 = 2, midway between 0.5 and 3.5) and find f(x1) and f(x1 + delta) where delta is small enough. If f(x1 + delta) > f(x1) it means that the peak is towards the right of x1 otherwise it is towards the left.

Carry out binary search and come to a close enough value of the peak as you want.

You can modify the above approach by choosing the next x_t according to the difference f(x1 + delta) - f(x1).

Upvotes: 1

Related Questions