Minimum Global

MKL.NET.Optimization now has a global minimum algorithm.

According to the no free lunch theorem it is not possible to have a superior optimisation algorithm when averaged across all possible problems. With this encouraging input I started to think about the properties that would be useful in a global minimum algorithm.

One idea that came to mind was that a sequence of finer and finer grids of starting points using the local BFGS Minimum function would eventually find the global minimum. It would also find the global minimum for simpler surfaces earlier in the search sequence. For performance each iteration's grid of starting points could be run in parallel.

After thinking a lot about what the grid size each iteration should have, I realised it's a bit like a game of battleships where you don't know the size of the ships. If the local BFGS search is close enough it will find its way to the minima. So the grid search sequence should try to keep reducing the maximum distance between any point in the space to the closest search point.

The most efficient start is a single search point in the centre of the n dimensional space. Next are the \(2^n\) points that bisect the diagonals to the centre. Then the \(2^n\) bisecting points around each of the previous iteration's points and so on.

This sequence has been implemented as a sequence of MinimumIteration in a sync and async form. Functions have also been included with a stopping criteria of time and/or number of same minimum value iterations.

These test functions have been used to test the algorithm. The following results were produced running all problems in parallel with a stopping criteria of 4 same iteration or overall time of 20 minutes.

Running 15 (out of 1,526) tests for 1 iterations on 15 threads.
minimum_global.rastrigin
  INFO: time = 0.1 next = 0.1 fmin = +1.98992 xmin = [0.9949586378394885, 0.9949586378394885]
  INFO: time = 0.1 next = 0.1 fmin = +1.98992 xmin = [0.9949586378394885, 0.9949586378394885]
  INFO: time = 0.0 next = 0.2 fmin = +1.98992 xmin = [0.9949586378394885, 0.9949586378394885]
  INFO: time = 0.1 next = 0.5 fmin = +0.00000 xmin = [2.386471478765806E-09, 2.386471478765806E-09]
  INFO: time = 0.1 next = 0.2 fmin = +0.00000 xmin = [-2.9653389804957554E-10, -4.184096382895113E-10]
  INFO: time = 0.4 next = 1.5 fmin = +0.00000 xmin = [-2.9653389804957554E-10, -4.184096382895113E-10]
  INFO: time = 1.1 next = 4.6 fmin = +0.00000 xmin = [-2.9653389804957554E-10, -4.184096382895113E-10]
minimum_global.ackley
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [3.3839161472926094E-09, 3.3839161472926094E-09]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [3.3839161472926094E-09, 3.3839161472926094E-09]
  INFO: time = 0.1 next = 0.2 fmin = +0.00000 xmin = [3.3839161472926094E-09, 3.3839161472926094E-09]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [3.3839161472926094E-09, 3.3839161472926094E-09]
minimum_global.rosenbrock
  INFO: time = 0.1 next = 0.1 fmin = +0.00000 xmin = [0.9999986657753233, 0.9999973809080209]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [1.0000001348047385, 1.0000002954781022]
  INFO: time = 0.1 next = 0.3 fmin = +0.00000 xmin = [0.9999999491710393, 0.9999998761252349]
  INFO: time = 0.1 next = 0.4 fmin = +0.00000 xmin = [0.9999998182525037, 0.9999996318431258]
minimum_global.beale
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [2.9999998294895387, 0.4999999536661821]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [2.999999955445457, 0.49999998385430106]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [2.9999999941267395, 0.4999999997470144]
  INFO: time = 0.1 next = 0.3 fmin = +0.00000 xmin = [2.999999998139205, 0.500000000027005]
minimum_global.bukin6
  INFO: time = 0.1 next = 0.1 fmin = +0.00860 xmin = [-9.807806209940138, 0.961930622059657]
  INFO: time = 0.0 next = 0.0 fmin = +0.00860 xmin = [-9.807806209940138, 0.961930622059657]
  INFO: time = 0.0 next = 0.0 fmin = +0.00860 xmin = [-9.807806209940138, 0.961930622059657]
  INFO: time = 0.0 next = 0.0 fmin = +0.00670 xmin = [-10.624203064867034, 1.1287369076147096]
  INFO: time = 0.3 next = 1.1 fmin = +0.00423 xmin = [-9.687302495526835, 0.9384382962760216]
  INFO: time = 0.5 next = 2.0 fmin = +0.00090 xmin = [-10.041136295166881, 1.0082441810048306]
  INFO: time = 1.3 next = 5.0 fmin = +0.00090 xmin = [-10.041136295166881, 1.0082441810048306]
  INFO: time = 2.3 next = 9.3 fmin = +0.00090 xmin = [-10.041136295166881, 1.0082441810048306]
  INFO: time = 8.5 next = 34.0 fmin = +0.00042 xmin = [-9.975240688716555, 0.9950542679811764]
  INFO: time = 36.0 next = 143.9 fmin = +0.00042 xmin = [-9.975240688716555, 0.9950542679811764]
  INFO: time = 133.0 next = 531.9 fmin = +0.00025 xmin = [-9.998885572489371, 0.9997771269228957]
  INFO: time = 332.1 next = 1328.5 fmin = +0.00011 xmin = [-10.004816488523078, 1.0009635296898276]
  INFO: time = 686.0 next = 0.0 fmin = +0.00011 xmin = [-10.004816488523078, 1.0009635296898276]
minimum_global.levi13
  INFO: time = 0.1 next = 0.1 fmin = +1.98303 xmin = [0.005736757039913081, 0.011378532059834648]
  INFO: time = 0.0 next = 0.0 fmin = +1.98303 xmin = [0.005736757039913081, 0.011378532059834648]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [1.0000000036810488, 1.0000000274074299]
  INFO: time = 0.3 next = 1.0 fmin = +0.00000 xmin = [0.9999999994681851, 1.000000004107341]
  INFO: time = 0.1 next = 0.4 fmin = +0.00000 xmin = [1.0000000001245366, 1.0000000020245596]
  INFO: time = 0.5 next = 1.8 fmin = +0.00000 xmin = [0.9999999999951217, 1.0000000003536822]
minimum_global.himmelblau
  INFO: time = 0.1 next = 0.1 fmin = +0.00000 xmin = [3.00000002153875, 1.9999999996211888]
  INFO: time = 0.0 next = 0.0 fmin = +0.00000 xmin = [-3.7793102435231836, -3.2831859858075685]
  INFO: time = 0.0 next = 0.1 fmin = +0.00000 xmin = [-2.805118088674678, 3.1313125182517605]
  INFO: time = 0.0 next = 0.1 fmin = +0.00000 xmin = [3.584428340112484, -1.8481265264472644]
minimum_global.easom
  INFO: time = 0.0 next = 0.0 fmin = -1.00000 xmin = [3.141592671360607, 3.141592671360607]
  INFO: time = 0.1 next = 0.1 fmin = -1.00000 xmin = [3.1415926535911787, 3.1415926535911787]
  INFO: time = 0.4 next = 1.7 fmin = -1.00000 xmin = [3.1415926535911787, 3.1415926535911787]
  INFO: time = 0.2 next = 0.6 fmin = -1.00000 xmin = [3.1415926535911787, 3.1415926535911787]
minimum_global.crossintray
  INFO: time = 0.0 next = 0.0 fmin = -0.00010 xmin = [0, 0]
  INFO: time = 0.0 next = 0.0 fmin = -1.79060 xmin = [4.490999229124073, 4.490999229124073]
  INFO: time = 0.0 next = 0.1 fmin = -2.06261 xmin = [1.3494065690571644, 1.3494065690571644]
  INFO: time = 0.2 next = 0.8 fmin = -2.06261 xmin = [1.3494065690571644, 1.3494065690571644]
  INFO: time = 0.1 next = 0.4 fmin = -2.06261 xmin = [-1.3494066323708354, -1.3494066323708354]
  INFO: time = 0.7 next = 2.7 fmin = -2.06261 xmin = [-1.3494066323708354, -1.3494066323708354]
minimum_global.eggholder
  INFO: time = 0.1 next = 0.1 fmin = -66.84372 xmin = [8.456934407364127, 15.650918244004314]
  INFO: time = 0.1 next = 0.1 fmin = -559.78686 xmin = [-242.97925178232745, 274.38032908558876]
  INFO: time = 0.1 next = 0.6 fmin = -935.33795 xmin = [439.4809966756544, 453.9774342118226]
  INFO: time = 0.1 next = 0.6 fmin = -935.33795 xmin = [439.4809966756544, 453.9774342118226]
  INFO: time = 0.5 next = 2.2 fmin = -957.12165 xmin = [511.9999999970895, 405.7134987637949]
  INFO: time = 0.8 next = 3.4 fmin = -959.64064 xmin = [511.9999999875001, 404.22703322635886]
  INFO: time = 1.8 next = 7.3 fmin = -959.64066 xmin = [511.9999999855185, 404.23305453191966]
  INFO: time = 3.9 next = 15.4 fmin = -959.64066 xmin = [511.999999990171, 404.2318044375143]
  INFO: time = 16.1 next = 64.2 fmin = -959.64066 xmin = [511.999999990171, 404.2318044375143]
  INFO: time = 88.3 next = 353.0 fmin = -959.64066 xmin = [511.9999999949194, 404.23182568889445]
minimum_global.holder
  INFO: time = 0.0 next = 0.0 fmin = -1.73297 xmin = [1.2626272073096718, 0]
  INFO: time = 0.1 next = 0.1 fmin = -11.06955 xmin = [4.853855860531211, 9.702113907125167]
  INFO: time = 0.0 next = 0.1 fmin = -11.06955 xmin = [-4.8538558433843315, -9.702113889157784]
  INFO: time = 0.1 next = 0.5 fmin = -19.20850 xmin = [8.055023477564395, 9.664589973778838]
  INFO: time = 0.3 next = 1.3 fmin = -19.20850 xmin = [-8.055023496727005, -9.664589995913872]
  INFO: time = 0.7 next = 2.6 fmin = -19.20850 xmin = [8.055023454533762, 9.664590005300033]
  INFO: time = 1.2 next = 4.9 fmin = -19.20850 xmin = [-8.055023468586946, -9.664590020713243]
minimum_global.mccormick
  INFO: time = 0.0 next = 0.0 fmin = -1.91322 xmin = [-0.5471975842759544, -1.5471975714832213]
  INFO: time = 0.1 next = 0.1 fmin = -1.91322 xmin = [-0.547197557916689, -1.5471975289171152]
  INFO: time = 0.1 next = 0.4 fmin = -1.91322 xmin = [-0.547197552156416, -1.547197551042736]
  INFO: time = 0.0 next = 0.0 fmin = -1.91322 xmin = [-0.547197552156416, -1.547197551042736]
minimum_global.schaffer2
  INFO: time = 0.3 next = 0.3 fmin = +0.23509 xmin = [19.335179384482107, -3.0155700873323715E-06]
  INFO: time = 329.9 next = 329.9 fmin = +0.23509 xmin = [19.335179384482107, -3.0155700873323715E-06]
  INFO: time = 869.9 next = 0.0 fmin = +0.14225 xmin = [1.2534911725942382E-08, -13.498590702548569]
minimum_global.schaffer4
  INFO: time = 0.2 next = 0.2 fmin = +0.29258 xmin = [1.2531318244654337, -1.05369468038922E-06]
  INFO: time = 91.8 next = 91.8 fmin = +0.29258 xmin = [1.2531318284190727, -1.1098138909324352E-07]
  INFO: time = 1108.0 next = 0.0 fmin = +0.29258 xmin = [1.2531318284190727, -1.1098138909324352E-07]
minimum_global.styblinski_tang
  INFO: time = 0.1 next = 0.1 fmin = -78.33233 xmin = [-2.903534001415568, -2.903534001415568]
  INFO: time = 0.0 next = 0.0 fmin = -78.33233 xmin = [-2.9035340256020716, -2.9035340256020716]
  INFO: time = 0.0 next = 0.1 fmin = -78.33233 xmin = [-2.9035340256020716, -2.9035340256020716]
  INFO: time = 0.0 next = 0.0 fmin = -78.33233 xmin = [-2.9035340256020716, -2.9035340256020716]
Maximum memory usage was 12,512 KB (limit set at 102,400 KB).
15 tests run in 1,200 seconds: 15 passed, 0 failed, 0 skipped. Success!

MKL.NET.Optimization now covers the majority of scipy.optimize functionality with high performance algorithms. Version 1.0.0 has been released.