1

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.

1
  • 2
    "there are no restrictions on the function": this is an unrealistic statement. In such a case the only approach is exhaustive search. Be ready for 2^64 function evaluations.
    – user1196549
    Feb 16, 2016 at 16:50

2 Answers 2

1

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.

6
  • True. Could my question have a reasonable answer if I'd tighten the constraints? (i.e. considering classes of functions almost everywhere equal, so to even out pathological cases) Feb 16, 2016 at 16:51
  • @marcotrevi Yes: perhaps for continuous, smooth, or Lipschitz functions, the question makes sense.
    – Gassa
    Feb 16, 2016 at 16:54
  • @marcotrevi You may have to define the domain, like real values in [0..1], as well.
    – Gassa
    Feb 16, 2016 at 16:55
  • Thank you. I'll post another question then, since on this one there are already your answers. Feb 16, 2016 at 16:56
  • @Gassa: simple continuity doesn't really help. Think of sin(x)+1/((x-m)²+1000). For a global optimum, local conditions aren't sufficient.
    – user1196549
    Feb 16, 2016 at 16:58
1

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.

2
  • I suspect that that function is mathematically ill-defined, as it depends on the algorithm... Feb 16, 2016 at 16:48
  • 1
    @marcotrevi We can rephrase it this way. 1. Take any algorithm. 2. Wait until it finishes execution. 3. Then, there exists a function (one such function is defined in the answer) on which the output of the algorithm is wrong. Therefore, no "right" algorithm exists.
    – Gassa
    Feb 16, 2016 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.