3
$\begingroup$

I designed an algorithm to find the global minimum of a function and implemented it in MATLAB. And I also implemented the "Tunneling algorithm" for the global minimum of a function in MATLAB.

But now, I want an intelligent way to compare these two algorithms and see which one gets to the global minimum faster. Using the MATLAB tic toc isn't enough. How can I do it?

$\endgroup$
  • $\begingroup$ Code written in a high-level language such as matlab is highly sensitive to implementation and even matlab version differences. You cannot draw meaningful conclusions from such benchmarks, unfortunately. $\endgroup$ – Anony-Mousse Sep 16 '15 at 6:41
  • 1
    $\begingroup$ @Anony-Mousse -- that's simply not true on so many levels. $\endgroup$ – Wolfgang Bangerth Sep 16 '15 at 11:11
  • $\begingroup$ @WolfgangBangerth benchmark the same code in, say, Octave, and you most likely get a very different result. Been there, done that. Benchmarks on this level are largely random. Use a language that predictably compiles into binary, such as C or C++, and gives you the control where you need it. $\endgroup$ – Anony-Mousse Sep 16 '15 at 11:41
  • $\begingroup$ @Anony-Mousse I don't argue that with matlab or similar, you may not get exact reproducibility of milliseconds. But that's not what the original question was about. The question was how to compare two algorithms, and I see absolutely no reason why that couldn't be done in Matlab. See my answer below for one way. But even if you chose to compare different algorithms for their run time, I would still think that there is sufficient information to draw educated conclusions. $\endgroup$ – Wolfgang Bangerth Sep 16 '15 at 18:08
  • $\begingroup$ I'm seeing several orders of performance of difference in implementations. This masks any true advantage unless it is O(n) vs. O(n^2) - which you barely ever see, because the complexity usually mostly depends on the problem, not the solution. And people don't run n high enough either to reach this area. $\endgroup$ – Anony-Mousse Sep 16 '15 at 18:47
8
$\begingroup$

The usual approach to testing optimization algorithms is to compare how many function evaluations they need to find the minimum (or get within a fixed tolerance $\varepsilon$ of the minimum). This is easily implemented in any code, and it does not matter in that case how fast your computer is, or what the resolution of the tic/toc mechanism is.

There are a number of standard problems that are often considered in the optimization literature. The simplest one would be the Rosenbrock function, see https://en.wikipedia.org/wiki/Rosenbrock_function .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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