2

I have a few optimization algorithms (for finding function minimum) and I'd like to check how good they are. Suppose I build test cases and compare the actual results to theoretical ones. What measures should I use to estimate if the function minimum was actually found?

I thought about:

  • mean number of function evaluations (± standard deviation)
  • success rate (how often it actually finds minimum)

Are there any others that I have missed (let's say algorithm finishes 1e-4 from known solution. so is it success already or not?)

My main concern is not time complexity. It is algorithm accuracy in cases when exact solution might never be found (eg. multidimensional solution spaces). How do I calculate the rate of convergence?

  • 1
    What do you mean by "good?" How do you define "success?" – Robert Harvey Aug 25 '14 at 21:36
  • @RobertHarvey success is when function minimum is found (for known test functions). – alex Aug 25 '14 at 21:40
  • Build test cases. Compare your output to the expected output. – Adam Zuckerman Aug 26 '14 at 1:34
  • There is answer to your question: please read Fixed-point iteration. Basically, first step is to understand the region of convergence of your approach, and then for a given point, calculate the rate of convergence. – rwong Aug 26 '14 at 10:27
2

The simple way to tell how "close" one solution is to another is to determine its standard error.

Standard error is the standard deviation of answers you get. Then you divide the distance between two solutions by the standard error. If the answer is less than 1, that's pretty close, because you could get that big of a difference just by randomness. If less than 2, that's still respectable. Beyond 2, you say no, not close.

Another way is to get the second derivative of the solution with respect to whatever you're varying. That second derivative represents the "sharpness" of the solution, and the standard error is proportional to the inverse square root of that.

If you like math, look here and here.

2
  1. Figure out the complexity of the algorithm (its Big O)
  2. Measure the time it takes to perform one iteration (if it is constant), or measure several iterations and amortize the time it takes.

That's it.

To get the running time for a particular n, just take the amount of time for 1 iteration, and plug it into your big O. So, for example, if your Big O is O(n^2), and one iteration takes 100 milliseconds, then running time for n=6 will be 10 seconds.

  • This is why we have Big O. – user22815 Aug 25 '14 at 22:26

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.