CODEWITHSUNDEEP
algorithmoptimizationbenchmarkingminimization
marco trevi
marco trevi

Reputation: 241

Benchmark for fast algorithms whose task is function minimization

Is there a set of test functions to measure the performance (in terms of speed, maybe trading off with accuracy) of a given algorithm whose task is to find a/the global minimum of a real-valued function over a given interval? Eventually: is this problem an open problem or does there exist a theoretical best algorithm for such a task?

EDIT: there are no restrictions on the function, other that it should be bounded.

Upvotes: 1

Views: 77

Answers (2)

Gassa
Gassa

Reputation: 8846

With no restrictions on the function except boundedness, it does not seem possible to always find its global minimum, let alone in reasonable time.

Consider the family of real-valued functions defined on [0..1]:

f (x0) = y0
f (x)  = 0    for all other x in [0..1]

For any fixed x0 in [0..1] and y0 < 0, the minimum is at x0. Still, any algorithm with no prior knowledge of x0 will have a hard time finding it.

Upvotes: 1

gnasher729
gnasher729

Reputation: 52538

Take a function that is 0 in every point where you evaluate f (x), and c for an unknown c > 0 for every point where you don't evaluate f (x). If you want it continuous, then if x is between a and b, where a and b are the neighbouring points where you evaluated f (a) and f (b), then f goes linear from f (a) = 0 to f ((a + b)/2) = c and back linear to f (b) = 0.

Clearly every time you evaluate f (x), you get a zero. Since you never evaluate anything else, your algorithm cannot conclude that the global maximum is anything but zero - which is wrong.

Upvotes: 1

Related Questions