Global Optimization Benchmarks

Dear SciPy developers & users, I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!). In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing. Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot. I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers? Any suggestion is more than welcome. Andrea.

Dear Andrea, SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points. A script to use 100 sampling points in a single iteration with the sobol sampling method: ``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ``` If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds. Please let me know if you need any help. Best regards, Stefan Endres On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea. _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering) Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/

Hi Stefan, On Sun, 26 Jul 2020 at 17.19, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Dear Andrea,
SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points.
A script to use 100 sampling points in a single iteration with the sobol sampling method:
``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ```
If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds.
Please let me know if you need any help.
Thank you for your answer. The approach I had several years ago - and that I’d like to keep - was to generate 100 random starting points for each benchmark and run all the global optimizers from that point: see http://infinity77.net/global_optimization/ Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks. I have now a few more benchmark functions plus a couple of new algorithms and I’d like to take the same steps. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. Shrinking the bounds is of course always a possibility but it makes life easier to the algorithms and it will fail as a strategy if a benchmark has a global optimum exactly at (one or more of) the original bounds. That said, I didn’t know that the sampling process of SHGO relied on random numbers: that is good to know, as an alternative I can do as you suggested and vary the seed 100 times - one of the new algorithms I have also does not use an initial point so it was already my strategy to change the seed for that one. I can simply do the same for SHGO. I’m running still with an old Python/Numpy/SciPy combination (for legacy reasons) so I’ll have to see if differential_evolution and dual_annealing can be simply copied over locally and run - I tested SHGO and it runs with no problem. Andrea.
Best regards, Stefan Endres
On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea.
_______________________________________________
SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany <https://www.google.com/maps/search/Badgasteiner+Stra%C3%9Fe+3,+28359+Bremen,+Germany?entry=gmail&source=g> Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev

Hi Andrea, Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks. These criteria can be set with the following arguments: options = {'maxfev': 2000, 'f_min': f_min, 'f_tol': f_tol} result = shgo(obj_fun, bounds, n=30, sampling_method='sobol', options=options) The algorithm should iterate (1 iteration is: check stopping criteria --> sample `n` points --> triangulate --> find minimisers) until a global minimum within the specified tolerance is found or the number of function evaluations run out. A lower number of sampling points per iteration tends to show higher performance, but I know that there is a strange bug where the algorithm keeps running within the same attractor even if this is supposed to be added to the triangulation, so a higher`n` will work better on some test suites until this is fixed. Most people tend to use the non-iterative version of the algorithm which is the most stable so there might be a few bugs running it iteratively in general. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time I would also recommend looking into using GKLS generators which, to my understanding, is standard practice to avoid this kind of bias ( https://dl.acm.org/doi/10.1145/962437.962444 ) in benchmarking GO functions. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. At least for SHGO the NaN values (and other non-floating point objects) should not be a problem, it was partially developed to deal with discontinuities in the objective function. Returning a lower value might be an issue. SHGO is not supposed to be able to escape the bounds, but if the bounds fed to it are outside the actual bounds I think a strong penalty function would need to be added to the objective function or the algorithm will terminate earlier with the lower optimum. Another reason why I would recommend adding randomness to the objective functions (using something like GKLS) instead of the hyperparameters/bounds is that the sequences might lose their low-discrepancy properties with different seeds, but I am not an expert on how adjusting those sequences affects performance. I didn’t know that the sampling process of SHGO relied on random numbers The Sobol sequence is technically quasi random, but a true random number generator can also be used by specifying a random sampling function to the sample_method argument, the main difference being that most RNGs are biased towards the centre of the hypercube. On the other hand default sampling behaviour relies on sub-triangulations of the hyperrectangle (similar to DIRECT), but the performance is almost identical to the Sobol sequence. Sub-triangulations are biased towards boundaries and centres depending on if the vertices or centroids are used in the actual sampling so I would not recommend this for your benchmarks. Best regards, Stefan Endres On Sun, Jul 26, 2020 at 5:49 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 17.19, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Dear Andrea,
SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points.
A script to use 100 sampling points in a single iteration with the sobol sampling method:
``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ```
If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds.
Please let me know if you need any help.
Thank you for your answer. The approach I had several years ago - and that I’d like to keep - was to generate 100 random starting points for each benchmark and run all the global optimizers from that point: see http://infinity77.net/global_optimization/
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
I have now a few more benchmark functions plus a couple of new algorithms and I’d like to take the same steps. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. Shrinking the bounds is of course always a possibility but it makes life easier to the algorithms and it will fail as a strategy if a benchmark has a global optimum exactly at (one or more of) the original bounds.
That said, I didn’t know that the sampling process of SHGO relied on random numbers: that is good to know, as an alternative I can do as you suggested and vary the seed 100 times - one of the new algorithms I have also does not use an initial point so it was already my strategy to change the seed for that one. I can simply do the same for SHGO.
I’m running still with an old Python/Numpy/SciPy combination (for legacy reasons) so I’ll have to see if differential_evolution and dual_annealing can be simply copied over locally and run - I tested SHGO and it runs with no problem.
Andrea.
Best regards, Stefan Endres
On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea.
_______________________________________________
SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany <https://www.google.com/maps/search/Badgasteiner+Stra%C3%9Fe+3,+28359+Bremen,+Germany?entry=gmail&source=g> Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering) Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/

Hi Stefan, On Sun, 26 Jul 2020 at 19:48, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Hi Andrea,
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
These criteria can be set with the following arguments:
options = {'maxfev': 2000, 'f_min': f_min, 'f_tol': f_tol}
result = shgo(obj_fun, bounds, n=30, sampling_method='sobol', options=options)
The algorithm should iterate (1 iteration is: check stopping criteria --> sample `n` points --> triangulate --> find minimisers) until a global minimum within the specified tolerance is found or the number of function evaluations run out. A lower number of sampling points per iteration tends to show higher performance, but I know that there is a strange bug where the algorithm keeps running within the same attractor even if this is supposed to be added to the triangulation, so a higher`n` will work better on some test suites until this is fixed.
Most people tend to use the non-iterative version of the algorithm which is the most stable so there might be a few bugs running it iteratively in general.
I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time
I would also recommend looking into using GKLS generators which, to my understanding, is standard practice to avoid this kind of bias ( https://dl.acm.org/doi/10.1145/962437.962444 ) in benchmarking GO functions.
Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds.
At least for SHGO the NaN values (and other non-floating point objects) should not be a problem, it was partially developed to deal with discontinuities in the objective function. Returning a lower value might be an issue. SHGO is not supposed to be able to escape the bounds, but if the bounds fed to it are outside the actual bounds I think a strong penalty function would need to be added to the objective function or the algorithm will terminate earlier with the lower optimum.
Another reason why I would recommend adding randomness to the objective functions (using something like GKLS) instead of the hyperparameters/bounds is that the sequences might lose their low-discrepancy properties with different seeds, but I am not an expert on how adjusting those sequences affects performance.
I didn’t know that the sampling process of SHGO relied on random numbers
The Sobol sequence is technically quasi random, but a true random number generator can also be used by specifying a random sampling function to the sample_method argument, the main difference being that most RNGs are biased towards the centre of the hypercube. On the other hand default sampling behaviour relies on sub-triangulations of the hyperrectangle (similar to DIRECT), but the performance is almost identical to the Sobol sequence. Sub-triangulations are biased towards boundaries and centres depending on if the vertices or centroids are used in the actual sampling so I would not recommend this for your benchmarks.
Best regards,
Stefan Endres
Thank you for the detailed answer. I just run a very simple test using the Rosenbrock function, and I am sure I am doing something wrong here. Looking at the benchmark results on your webpage, it seems to me that SHGO is an extremely good algorithm: I have created this simple test: import numpy from shgo import shgo # -------------------------------------------------------------------------------- # class Rosenbrock(object): def __init__(self, dimensions=2): self.N = dimensions self.nfev = 0 self._bounds = zip([-30.] * self.N, [30.0] * self.N) self.global_optimum = [[1.0 for _ in range(self.N)]] self.fglob = 0.0 def fun(self, x, *args): self.nfev += 1 f = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) print (self.nfev, f) return f # -------------------------------------------------------------------------------------- # def Test(): maxfun = 2000 tolfun = 1e-2 numpy.random.seed(123456) benchmark = Rosenbrock() bounds = benchmark._bounds fglob = benchmark.fglob options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun} res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') xf, yf = res.x, res.fun print(xf, yf, fglob, benchmark.nfev) if __name__ == '__main__': Test() And I get the following numerical results and a graph of the evolution of the objective function: array([ 0.99999555, 0.99999111]), 1.9768160305004305e-11, 0.0, 2113 [image: image.png] I am probably too ignorant about SHGO, but I would have thought the Rosenbrock function to be an easy pick for SHGO - i.e., convergence to the global optimum achieved much faster than 2,000 evaluations. Maybe there are some settings that I should change? Andrea.
On Sun, Jul 26, 2020 at 5:49 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 17.19, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Dear Andrea,
SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points.
A script to use 100 sampling points in a single iteration with the sobol sampling method:
``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ```
If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds.
Please let me know if you need any help.
Thank you for your answer. The approach I had several years ago - and that I’d like to keep - was to generate 100 random starting points for each benchmark and run all the global optimizers from that point: see http://infinity77.net/global_optimization/
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
I have now a few more benchmark functions plus a couple of new algorithms and I’d like to take the same steps. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. Shrinking the bounds is of course always a possibility but it makes life easier to the algorithms and it will fail as a strategy if a benchmark has a global optimum exactly at (one or more of) the original bounds.
That said, I didn’t know that the sampling process of SHGO relied on random numbers: that is good to know, as an alternative I can do as you suggested and vary the seed 100 times - one of the new algorithms I have also does not use an initial point so it was already my strategy to change the seed for that one. I can simply do the same for SHGO.
I’m running still with an old Python/Numpy/SciPy combination (for legacy reasons) so I’ll have to see if differential_evolution and dual_annealing can be simply copied over locally and run - I tested SHGO and it runs with no problem.
Andrea.
Best regards, Stefan Endres
On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea.
_______________________________________________
SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany <https://www.google.com/maps/search/Badgasteiner+Stra%C3%9Fe+3,+28359+Bremen,+Germany?entry=gmail&source=g> Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev

Hi Andrea, Thank you for your continued patience and detailed response. I apologise this is really due to my poor documentation, I’m hoping to have more time to resolve that soon with use cases and examples. I forgot that for these performance benchmarks ideally use the minimize_every_iter option as well (this defaults to False because iterations are primarily used to track homology groups (mostly used in things like energy surfaces or vector field design with less thought to its performance as a GO algorithm)). When this is off the algorithm does not have a local exploration phase so this result is expected until the iterations finish and do a last refinement. I made the following adjustments to your script to include this option (also removed line using zip to be compatible with Python 3.8): import numpyfrom matplotlib import pyplot as plotfrom shgo import shgo # -------------------------------------------------------------------------------- # fun_l = [] # Global list for plot nfev_l = [] # Global list for plot class Rosenbrock(object): def __init__(self, dimensions=2): self.N = dimensions self.nfev = 0 # self._bounds = zip([-30.] * self.N, [30.0] * self.N) self._bounds = [(-30., 30.0),] * self.N self.global_optimum = [[1.0 for _ in range(self.N)]] self.fglob = 0.0 def fun(self, x, *args): self.nfev += 1 f = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) fun_l.append(f) # Append objective function values for plots nfev_l.append(self.nfev) # Append number of function eval values for plots return f # -------------------------------------------------------------------------------------- # def Test(): maxfun = 2000 tolfun = 1e-2 numpy.random.seed(123456) benchmark = Rosenbrock() bounds = benchmark._bounds fglob = benchmark.fglob options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun, 'minimize_every_iter': True} res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') xf, yf = res.x, res.fun print(xf, yf, fglob, benchmark.nfev) return if __name__ == '__main__': Test() # Plot results: plot.plot(nfev_l, fun_l) plot.show() Which produces the following output on Python 3.8 ( https://imgur.com/a/hMfbhW1): [image: image.png] So SHGO finds the global minimum with the performance in the publication results, *but* it does not terminate when it finds it, I believe this is related to the following warning: /home/stefan_endres/.local/lib/python3.8/site-packages/shgo/_shgo.py:986: RuntimeWarning: divide by zero encountered in double_scalars if (lres_f_min.fun - self.f_min_true) / abs( /home/stefan_endres/.local/lib/python3.8/site-packages/shgo/_shgo.py:823: RuntimeWarning: divide by zero encountered in double_scalars pe = (self.f_lowest - self.f_min_true) / abs(self.f_min_true) The `if` statement, which checks if the objective function is precisely zero, before checking the actual supplied value, was the culprit in this bug. It should be: if self.f_min_true == 0.0: if self.f_lowest == 0.0: ...to avoid the division by zero. However, fixing this produced other errors. Also when running this in Python 2 I also get the following outright division by zero error: [stefan_endres@primary shgo-gavana]$ python2 run.py Traceback (most recent call last): File "run.py", line 49, in <module> Test() File "run.py", line 42, in Test res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 423, in shgo shc.construct_complex() File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 728, in construct_complex self.iterate() File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 876, in iterate self.find_minima() # Process minimiser pool File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 749, in find_minima self.minimise_pool(self.local_iter) File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 987, in minimise_pool self.f_min_true) <= self.f_tol: ZeroDivisionError: float division by zero I apologise for these issues. To be frank, when I merged all the possible stopping criteria to streamline the code I did not re-run the benchmarks again to test if the performance profiles are reproduced. As I mentioned, most people who use SHGO tend to always use a single iteration version and tune sampling points until they find all solutions robustly in a problem class. So unfortunately I have been focussed on fixing bugs that arise in those instances when I have time to work on the code for the algorithm. The latest version should work with the stopping criteria, but some of the unittests are failing so I have not pushed it to the repository yet. Another possibility would be to use the Bitbucket version of SHGO with the scripts at the `jogo_Sobol` tag which was used for the publication and should also Python 2 compatible (using this together with the scripts to run the benchmarking performance profiles available on the `shgo-dev` repository). More ideally though I would like time to fix the new code, and possibly make it Python 2 compatible again (I dropped Python 2 support around the same time the SciPy project did), depending on your timeline for running these benchmarks. Best regards, Stefan Endres On Mon, Jul 27, 2020 at 9:00 AM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 19:48, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Hi Andrea,
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
These criteria can be set with the following arguments:
options = {'maxfev': 2000, 'f_min': f_min, 'f_tol': f_tol}
result = shgo(obj_fun, bounds, n=30, sampling_method='sobol', options=options)
The algorithm should iterate (1 iteration is: check stopping criteria --> sample `n` points --> triangulate --> find minimisers) until a global minimum within the specified tolerance is found or the number of function evaluations run out. A lower number of sampling points per iteration tends to show higher performance, but I know that there is a strange bug where the algorithm keeps running within the same attractor even if this is supposed to be added to the triangulation, so a higher`n` will work better on some test suites until this is fixed.
Most people tend to use the non-iterative version of the algorithm which is the most stable so there might be a few bugs running it iteratively in general.
I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time
I would also recommend looking into using GKLS generators which, to my understanding, is standard practice to avoid this kind of bias ( https://dl.acm.org/doi/10.1145/962437.962444 ) in benchmarking GO functions.
Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds.
At least for SHGO the NaN values (and other non-floating point objects) should not be a problem, it was partially developed to deal with discontinuities in the objective function. Returning a lower value might be an issue. SHGO is not supposed to be able to escape the bounds, but if the bounds fed to it are outside the actual bounds I think a strong penalty function would need to be added to the objective function or the algorithm will terminate earlier with the lower optimum.
Another reason why I would recommend adding randomness to the objective functions (using something like GKLS) instead of the hyperparameters/bounds is that the sequences might lose their low-discrepancy properties with different seeds, but I am not an expert on how adjusting those sequences affects performance.
I didn’t know that the sampling process of SHGO relied on random numbers
The Sobol sequence is technically quasi random, but a true random number generator can also be used by specifying a random sampling function to the sample_method argument, the main difference being that most RNGs are biased towards the centre of the hypercube. On the other hand default sampling behaviour relies on sub-triangulations of the hyperrectangle (similar to DIRECT), but the performance is almost identical to the Sobol sequence. Sub-triangulations are biased towards boundaries and centres depending on if the vertices or centroids are used in the actual sampling so I would not recommend this for your benchmarks.
Best regards,
Stefan Endres
Thank you for the detailed answer. I just run a very simple test using the Rosenbrock function, and I am sure I am doing something wrong here. Looking at the benchmark results on your webpage, it seems to me that SHGO is an extremely good algorithm: I have created this simple test:
import numpy from shgo import shgo
# -------------------------------------------------------------------------------- #
class Rosenbrock(object):
def __init__(self, dimensions=2):
self.N = dimensions self.nfev = 0 self._bounds = zip([-30.] * self.N, [30.0] * self.N)
self.global_optimum = [[1.0 for _ in range(self.N)]] self.fglob = 0.0
def fun(self, x, *args): self.nfev += 1 f = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) print (self.nfev, f) return f
# -------------------------------------------------------------------------------------- #
def Test():
maxfun = 2000 tolfun = 1e-2 numpy.random.seed(123456)
benchmark = Rosenbrock() bounds = benchmark._bounds fglob = benchmark.fglob
options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun} res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') xf, yf = res.x, res.fun
print(xf, yf, fglob, benchmark.nfev)
if __name__ == '__main__': Test()
And I get the following numerical results and a graph of the evolution of the objective function:
array([ 0.99999555, 0.99999111]), 1.9768160305004305e-11, 0.0, 2113
[image: image.png]
I am probably too ignorant about SHGO, but I would have thought the Rosenbrock function to be an easy pick for SHGO - i.e., convergence to the global optimum achieved much faster than 2,000 evaluations. Maybe there are some settings that I should change?
Andrea.
On Sun, Jul 26, 2020 at 5:49 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 17.19, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Dear Andrea,
SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points.
A script to use 100 sampling points in a single iteration with the sobol sampling method:
``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ```
If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds.
Please let me know if you need any help.
Thank you for your answer. The approach I had several years ago - and that I’d like to keep - was to generate 100 random starting points for each benchmark and run all the global optimizers from that point: see http://infinity77.net/global_optimization/
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
I have now a few more benchmark functions plus a couple of new algorithms and I’d like to take the same steps. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. Shrinking the bounds is of course always a possibility but it makes life easier to the algorithms and it will fail as a strategy if a benchmark has a global optimum exactly at (one or more of) the original bounds.
That said, I didn’t know that the sampling process of SHGO relied on random numbers: that is good to know, as an alternative I can do as you suggested and vary the seed 100 times - one of the new algorithms I have also does not use an initial point so it was already my strategy to change the seed for that one. I can simply do the same for SHGO.
I’m running still with an old Python/Numpy/SciPy combination (for legacy reasons) so I’ll have to see if differential_evolution and dual_annealing can be simply copied over locally and run - I tested SHGO and it runs with no problem.
Andrea.
Best regards, Stefan Endres
On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea.
_______________________________________________
SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany <https://www.google.com/maps/search/Badgasteiner+Stra%C3%9Fe+3,+28359+Bremen,+Germany?entry=gmail&source=g> Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering) Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/

Hello everyone, A quick lunch break update on the above comments, I’ve fixed the above mentioned bugs in the main SHGO repository: https://github.com/Stefan-Endres/shgo running options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun, 'minimize_every_iter': True} res = shgo(benchmark.fun, bounds, n=20, options=options, sampling_method='simplicial') # Added a lower `n` argument, in general 20-30 per iteration produces better performance than 100 produces the expected output: [image: image.png] And the algorithm correctly terminates as expected. I'm still working on making it compatible with Python 2, but unfortunately ran out of time, I will try again later tonight. Regards, Stefan Endres On Mon, Jul 27, 2020 at 11:47 AM Stefan Endres <stefan.c.endres@gmail.com> wrote:
Hi Andrea,
Thank you for your continued patience and detailed response. I apologise this is really due to my poor documentation, I’m hoping to have more time to resolve that soon with use cases and examples.
I forgot that for these performance benchmarks ideally use the minimize_every_iter option as well (this defaults to False because iterations are primarily used to track homology groups (mostly used in things like energy surfaces or vector field design with less thought to its performance as a GO algorithm)). When this is off the algorithm does not have a local exploration phase so this result is expected until the iterations finish and do a last refinement.
I made the following adjustments to your script to include this option (also removed line using zip to be compatible with Python 3.8):
import numpyfrom matplotlib import pyplot as plotfrom shgo import shgo # -------------------------------------------------------------------------------- #
fun_l = [] # Global list for plot nfev_l = [] # Global list for plot class Rosenbrock(object):
def __init__(self, dimensions=2):
self.N = dimensions self.nfev = 0 # self._bounds = zip([-30.] * self.N, [30.0] * self.N) self._bounds = [(-30., 30.0),] * self.N self.global_optimum = [[1.0 for _ in range(self.N)]] self.fglob = 0.0
def fun(self, x, *args): self.nfev += 1 f = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) fun_l.append(f) # Append objective function values for plots nfev_l.append(self.nfev) # Append number of function eval values for plots return f # -------------------------------------------------------------------------------------- # def Test():
maxfun = 2000 tolfun = 1e-2 numpy.random.seed(123456)
benchmark = Rosenbrock() bounds = benchmark._bounds fglob = benchmark.fglob
options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun, 'minimize_every_iter': True} res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') xf, yf = res.x, res.fun print(xf, yf, fglob, benchmark.nfev) return if __name__ == '__main__': Test() # Plot results: plot.plot(nfev_l, fun_l) plot.show()
Which produces the following output on Python 3.8 ( https://imgur.com/a/hMfbhW1): [image: image.png]
So SHGO finds the global minimum with the performance in the publication results, *but* it does not terminate when it finds it, I believe this is related to the following warning:
/home/stefan_endres/.local/lib/python3.8/site-packages/shgo/_shgo.py:986: RuntimeWarning: divide by zero encountered in double_scalars if (lres_f_min.fun - self.f_min_true) / abs( /home/stefan_endres/.local/lib/python3.8/site-packages/shgo/_shgo.py:823: RuntimeWarning: divide by zero encountered in double_scalars pe = (self.f_lowest - self.f_min_true) / abs(self.f_min_true)
The `if` statement, which checks if the objective function is precisely zero, before checking the actual supplied value, was the culprit in this bug. It should be:
if self.f_min_true == 0.0: if self.f_lowest == 0.0:
...to avoid the division by zero. However, fixing this produced other errors. Also when running this in Python 2 I also get the following outright division by zero error:
[stefan_endres@primary shgo-gavana]$ python2 run.py Traceback (most recent call last): File "run.py", line 49, in <module> Test() File "run.py", line 42, in Test res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 423, in shgo shc.construct_complex() File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 728, in construct_complex self.iterate() File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 876, in iterate self.find_minima() # Process minimiser pool File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 749, in find_minima self.minimise_pool(self.local_iter) File "/home/stefan_endres/.local/lib/python2.7/site-packages/shgo/_shgo.py", line 987, in minimise_pool self.f_min_true) <= self.f_tol: ZeroDivisionError: float division by zero
I apologise for these issues. To be frank, when I merged all the possible stopping criteria to streamline the code I did not re-run the benchmarks again to test if the performance profiles are reproduced. As I mentioned, most people who use SHGO tend to always use a single iteration version and tune sampling points until they find all solutions robustly in a problem class. So unfortunately I have been focussed on fixing bugs that arise in those instances when I have time to work on the code for the algorithm. The latest version should work with the stopping criteria, but some of the unittests are failing so I have not pushed it to the repository yet.
Another possibility would be to use the Bitbucket version of SHGO with the scripts at the `jogo_Sobol` tag which was used for the publication and should also Python 2 compatible (using this together with the scripts to run the benchmarking performance profiles available on the `shgo-dev` repository).
More ideally though I would like time to fix the new code, and possibly make it Python 2 compatible again (I dropped Python 2 support around the same time the SciPy project did), depending on your timeline for running these benchmarks.
Best regards,
Stefan Endres
On Mon, Jul 27, 2020 at 9:00 AM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 19:48, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Hi Andrea,
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
These criteria can be set with the following arguments:
options = {'maxfev': 2000, 'f_min': f_min, 'f_tol': f_tol}
result = shgo(obj_fun, bounds, n=30, sampling_method='sobol', options=options)
The algorithm should iterate (1 iteration is: check stopping criteria --> sample `n` points --> triangulate --> find minimisers) until a global minimum within the specified tolerance is found or the number of function evaluations run out. A lower number of sampling points per iteration tends to show higher performance, but I know that there is a strange bug where the algorithm keeps running within the same attractor even if this is supposed to be added to the triangulation, so a higher`n` will work better on some test suites until this is fixed.
Most people tend to use the non-iterative version of the algorithm which is the most stable so there might be a few bugs running it iteratively in general.
I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time
I would also recommend looking into using GKLS generators which, to my understanding, is standard practice to avoid this kind of bias ( https://dl.acm.org/doi/10.1145/962437.962444 ) in benchmarking GO functions.
Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds.
At least for SHGO the NaN values (and other non-floating point objects) should not be a problem, it was partially developed to deal with discontinuities in the objective function. Returning a lower value might be an issue. SHGO is not supposed to be able to escape the bounds, but if the bounds fed to it are outside the actual bounds I think a strong penalty function would need to be added to the objective function or the algorithm will terminate earlier with the lower optimum.
Another reason why I would recommend adding randomness to the objective functions (using something like GKLS) instead of the hyperparameters/bounds is that the sequences might lose their low-discrepancy properties with different seeds, but I am not an expert on how adjusting those sequences affects performance.
I didn’t know that the sampling process of SHGO relied on random numbers
The Sobol sequence is technically quasi random, but a true random number generator can also be used by specifying a random sampling function to the sample_method argument, the main difference being that most RNGs are biased towards the centre of the hypercube. On the other hand default sampling behaviour relies on sub-triangulations of the hyperrectangle (similar to DIRECT), but the performance is almost identical to the Sobol sequence. Sub-triangulations are biased towards boundaries and centres depending on if the vertices or centroids are used in the actual sampling so I would not recommend this for your benchmarks.
Best regards,
Stefan Endres
Thank you for the detailed answer. I just run a very simple test using the Rosenbrock function, and I am sure I am doing something wrong here. Looking at the benchmark results on your webpage, it seems to me that SHGO is an extremely good algorithm: I have created this simple test:
import numpy from shgo import shgo
# -------------------------------------------------------------------------------- #
class Rosenbrock(object):
def __init__(self, dimensions=2):
self.N = dimensions self.nfev = 0 self._bounds = zip([-30.] * self.N, [30.0] * self.N)
self.global_optimum = [[1.0 for _ in range(self.N)]] self.fglob = 0.0
def fun(self, x, *args): self.nfev += 1 f = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) print (self.nfev, f) return f
# -------------------------------------------------------------------------------------- #
def Test():
maxfun = 2000 tolfun = 1e-2 numpy.random.seed(123456)
benchmark = Rosenbrock() bounds = benchmark._bounds fglob = benchmark.fglob
options = {'maxfev': maxfun, 'f_min': fglob, 'f_tol': tolfun} res = shgo(benchmark.fun, bounds, options=options, sampling_method='simplicial') xf, yf = res.x, res.fun
print(xf, yf, fglob, benchmark.nfev)
if __name__ == '__main__': Test()
And I get the following numerical results and a graph of the evolution of the objective function:
array([ 0.99999555, 0.99999111]), 1.9768160305004305e-11, 0.0, 2113
[image: image.png]
I am probably too ignorant about SHGO, but I would have thought the Rosenbrock function to be an easy pick for SHGO - i.e., convergence to the global optimum achieved much faster than 2,000 evaluations. Maybe there are some settings that I should change?
Andrea.
On Sun, Jul 26, 2020 at 5:49 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Hi Stefan,
On Sun, 26 Jul 2020 at 17.19, Stefan Endres <stefan.c.endres@gmail.com> wrote:
Dear Andrea,
SHGO does not use an initial starting point, only the bounds (which may also be specified as none or infinite). The benchmarks that I ran used for the publication used the global minimum as a stopping criteria (together with performance profiles that demonstrate the final results). For this particular benchmarking framework I would propose simply using a single iteration ((dim)^2 +1 points) or specifying 100 starting points.
A script to use 100 sampling points in a single iteration with the sobol sampling method:
``` result = shgo(obj_fun, bounds, n=100, sampling_method='sobol') ```
If you would like to add a more stochastic element to this performance I think the best approach would be to use a different seed for the sampling method (in my experience this does not make much of a difference to the performance in low dimensional problems), otherwise run shgo only once and/or with increasing numbers of iterations. Another possibility is to add a stochastic element to the bounds.
Please let me know if you need any help.
Thank you for your answer. The approach I had several years ago - and that I’d like to keep - was to generate 100 random starting points for each benchmark and run all the global optimizers from that point: see http://infinity77.net/global_optimization/
Those benchmarks also relied on the global optimum as a stopping criterion plus a maximum number of objective function evaluations (2,000), whichever is reached first. Of course, reaching the maximum number of function evaluations without getting to the global optimum (plus a pre-specified tolerance) means a failure in the context of my original benchmarks.
I have now a few more benchmark functions plus a couple of new algorithms and I’d like to take the same steps. I also have a slightly different approach to bounds/global optima locations so that algorithms that rely on guessing global optima by running to the center of the domain (or on the bounds) will have a less easy life this time. Bounds-shifting is what I used to do but you have to be careful as some of the benchmark functions can be undefined outside those bounds (I.e., returning NaNs) or they can have lower global optima outside the bounds. Shrinking the bounds is of course always a possibility but it makes life easier to the algorithms and it will fail as a strategy if a benchmark has a global optimum exactly at (one or more of) the original bounds.
That said, I didn’t know that the sampling process of SHGO relied on random numbers: that is good to know, as an alternative I can do as you suggested and vary the seed 100 times - one of the new algorithms I have also does not use an initial point so it was already my strategy to change the seed for that one. I can simply do the same for SHGO.
I’m running still with an old Python/Numpy/SciPy combination (for legacy reasons) so I’ll have to see if differential_evolution and dual_annealing can be simply copied over locally and run - I tested SHGO and it runs with no problem.
Andrea.
Best regards, Stefan Endres
On Sun, Jul 26, 2020 at 4:06 PM Andrea Gavana <andrea.gavana@gmail.com> wrote:
Dear SciPy developers & users,
I have a couple of new derivative-free, global optimization algorithms I’ve been working on lately - plus some improvements to AMPGO and a few more benchmark functions - and I’d like to rerun the benchmarks as I did back in 2013 (!!!).
In doing so, I’d like to remove some of the least interesting/worst performing algorithms (Firefly, MLSL, Galileo, the original DE) and replace them with the ones currently available in SciPy - differential_evolution, SHGO and dual_annealing.
Everything seems good and dandy, but it appears to me that SHGO does not accept an initial point for the optimization process - which makes the whole “run the optimization from 100 different starting points for each benchmark” a bit moot.
I am no expert on SHGO, so maybe there is an alternative way to “simulate” the changing of the starting point for the optimization? Or maybe some other approach to make it consistent across optimizers?
Any suggestion is more than welcome.
Andrea.
_______________________________________________
SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany <https://www.google.com/maps/search/Badgasteiner+Stra%C3%9Fe+3,+28359+Bremen,+Germany?entry=gmail&source=g> Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/ _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering)
Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/
-- Stefan Endres (MEng, AMIChemE, BEng (Hons) Chemical Engineering) Wissenchaftlicher Mitarbetier: Leibniz Institute for Materials Engineering IWT, Badgasteiner Straße 3, 28359 Bremen, Germany Work phone (DE): +49 (0) 421 218 51238 Cellphone (DE): +49 (0) 160 949 86417 Cellphone (ZA): +27 (0) 82 972 42 89 E-mail (work): s.endres@iwt.uni-bremen.de Website: https://stefan-endres.github.io/
participants (2)
-
Andrea Gavana
-
Stefan Endres