Faster Nelder-Mead algorithm

[bicycle1885]

Related to #103, I've read some papers about the Nelder-Mead algorithm and implemented a variant called Adaptive Nelder-Mead Simplex (ANMS) algorithm. You can find the package at https://github.com/bicycle1885/ANMS.jl.

I hope this is merged to Optim.jl, so I compared the performance.

Compared functions were

• quadratic function: dot(x - 1, x - 1)
• multidimensional Rosenbrock function: http://en.wikipedia.org/wiki/Rosenbrock_function

with five different dimensions (n = [2, 5, 10, 20, 50]).

The result is as follows:

quadratic function:

--- ANMS ---
2: 
elapsed time: 0.010157602 seconds (157552 bytes allocated)
fmin => 0.0
5: 
elapsed time: 0.00133118 seconds (889680 bytes allocated)
fmin => 2.874692204466751e-8
10: 
elapsed time: 0.003661411 seconds (2564752 bytes allocated)
fmin => 5.704532655372583e-8
20: 
elapsed time: 0.011579524 seconds (8133728 bytes allocated)
fmin => 5.1698486524263214e-8
50: 
elapsed time: 0.068112864 seconds (42861936 bytes allocated)
fmin => 8.513696765777041e-8

--- Optim ---
2: 
elapsed time: 0.017564181 seconds (348568 bytes allocated)
fmin => 9.397767141614407e-10
5: 
elapsed time: 0.002295282 seconds (2651920 bytes allocated)
fmin => 1.3461476385934277e-9
10: 
elapsed time: 0.016708881 seconds (20459840 bytes allocated)
fmin => 1.142383173134101e-7
20: 
elapsed time: 0.115632867 seconds (108467840 bytes allocated, 38.78% gc time)
fmin => 5.944810588990531e-8
50: 
elapsed time: 2.397011401 seconds (2835856800 bytes allocated, 49.88% gc time)
fmin => 3.663031017751178e-8

rosenbrock function:

--- ANMS ---
2: 
elapsed time: 0.009974135 seconds (146488 bytes allocated)
fmin => 7.868156252247752e-9
5: 
elapsed time: 0.000866841 seconds (427600 bytes allocated)
fmin => 2.071245431037171e-8
10: 
elapsed time: 0.003445336 seconds (1678768 bytes allocated)
fmin => 3.996436273244788e-8
20: 
elapsed time: 0.016988347 seconds (6119008 bytes allocated)
fmin => 7.81905861025263e-8
50: 
elapsed time: 0.274938347 seconds (62309152 bytes allocated, 7.80% gc time)
fmin => 8.238820707411458e-7

--- Optim ---
2: 
elapsed time: 0.017885417 seconds (615528 bytes allocated)
fmin => 8.940245976539097e-10
5: 
elapsed time: 0.008627849 seconds (9746640 bytes allocated)
fmin => 1.250866767091252e-9
10: 
elapsed time: 0.099422094 seconds (84184160 bytes allocated, 27.03% gc time)
fmin => 0.010763954938890423
20: 
elapsed time: 0.822331694 seconds (754486560 bytes allocated, 42.30% gc time)
fmin => 0.7307076508015659
50: 
elapsed time: 31.874317729 seconds (36538050560 bytes allocated, 51.20% gc time)
fmin => 1.1993608845052381

ANMS.jl was faster and needed less memories in all cases, and the minimal function values were comparable. Moreover, ANMS.jl was able to minimize high dimensional (n > 20) Rosenbrock functions well.

The benchmark script and results are available at https://gist.github.com/bicycle1885/d0aaace2eab0ba9eec52. Please note that ANMS.jl was patched (https://gist.github.com/bicycle1885/d0aaace2eab0ba9eec52#file-anms-patch) to match an initial simplex and convergence criterion to those of Optim.jl.

I want to know what you think about my proposal and if you think more thorough benchmarks are needed, I'll do them as well.

Thank you.

---

Compared commits and benchmark environment

ANMS.jl: 8734a0a + patch Optim.jl: 3ccbae7ec8b3c908eef900df5142c0bd660617f3

julia> versioninfo()
Julia Version 0.3.5
Commit a05f87b* (2015-01-08 22:33 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin14.1.0)
  CPU: Intel(R) Core(TM) i5-4288U CPU @ 2.60GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas
  LIBM: libopenlibm
  LLVM: libLLVM-3.3

[IainNZ]

@bicycle1885 can you turn this into a pull request? It seems like a valuable addition

[bicycle1885]

@lainNZ I did it just now! Though not yet benchmarked. https://github.com/JuliaOpt/Optim.jl/pull/110.

[pkofod]

Fixed by #220