On Wed, Oct 10, 2012 at 2:55 PM, Ralf Gommers <ralf.gommers@gmail.com> wrote:

On Tue, Oct 9, 2012 at 11:30 PM, Jacob Stevenson <jstevenson131@gmail.com> wrote:

...

Hi everyone, I just submitted a pull request to incorporate a basinhopping routine in the optimize package. Basinhopping is a powerful algorithm, but all the hard work would be done by the minimizers that already exist in scipy.optimize, so the additional code needed is really not very much.

The following is from the documentation notes:

Basin hopping is a random algorithm which attempts to find the global minimum of a smooth scalar function of one or more variables. The algorithm was originally described by David Wales http://www-wales.ch.cam.ac.uk/ . The algorithm is iterative with each iteration composed of the following steps

1) random displacement of the coordinates

2) local minimization

3) accept or reject the new coordinates based on the minimized function value.

This global minimization method has been shown to be extremely efficient on a wide variety of problems in physics and chemistry. It is especially efficient when the function has many minima separated by large barriers. See the Cambridge Cluster Database http://www-wales.ch.cam.ac.uk/CCD.html for database of molecular systems that have been optimized primarily using basin hopping. This database includes minimization problems exceeding 300 degrees of freedom.

Thanks, Jake

p.s. this is my first post and first submission

Hi Jake, welcome!

It looks to me like basin hopping would be a nice addition to scipy.optimize. It looks quite similar to simulated annealing, which we already have, and may be more efficient for certain classes of problems. You're hinting at that already in the notes section, but more details on that comparison would be good to put in the docs. A benchmark comparing your algorithm with anneal() would be good to see also.

A comparison would be useful, but I think the differences are large enough that the relative benefits would depend a lot on the problem. Anneal has to many tuning parameters, and like most of these global optimizers they use a large number of function evaluations even close to the optimum. (my impression) My impression is that hybrid optimizers, like basinhopping, are much better for problems that have several local minima but still have a nice local behavior. Several of the problems in statsmodels would fall into this category. I sent a while ago a message to the user mailing list ("OT: global optimizati​on, hybrid global local search"). I think this kind of optimizers would be a good addition to scipy, and I would be glad to be able to use something more systematic than just picking several random starting values for local optimization. Josef <a user>

This PR made me wonder what other algorithms would be good to have, and what's out of scope for scipy. My feeling is that some similar stochastic algorithms to this one could be nice to have, but that other types of global optimizers are out of scope - there's OpenOpt, IPOPT, PyGMO, PyEvolve etc. for that.

Cheers, Ralf

_______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev

As far as i can tell, simulated annealing is quite out of touch with more modern optimization strategies. See http://scicomp.stackexchange.com/questions/3372/simulated-annealing-proof-of... and the references mentioned, so more optimization algorithms are good. But i think the scipy staff should decide the scope of scipy: either add almost every proved and usable algorithm with an python implementation or only the provide the most famous. I prefer the first way. OT things i would like to see in scipy, if anybody has too much time: * non-negative matrix factorization * a data fitting function, aka curve_fit on steroids. Maybe lmfit, kaptyn or mpfit. * an bouded linear least squares solver, like bvls. * Bayesian frequency estimation * NFFT

On 11.10.2012 04:20, Till Stensitzki wrote:

As far as i can tell, simulated annealing is quite out of touch with more modern optimization strategies.

In Bayesian statistics, Markov chain Monte Carlo is the standard integration tool. If you want a peak or a root instead of the integral, Metropolis-Hastings becomes simulated annealing. Sturla

Jacob Stevenson <jstevenson131 <at> gmail.com> writes:

I thought I would mention here on the mailing list that I redid the basin

hopping global optimisation

algorithm with a more advanced feature set. There are now two versions basinhopping, and basinhopping_advanced. I would be very interested which version people think is more appropriate for scipy.

hi Jacob, I would like to see its comparison with mlsl or psarms, that have similar algorithm (combination of local and global search) and Python API available. You could easily done it in OpenOpt framework ( http://openopt.org ), additional computation time is usually insufficient. There you could compare it with some other global solvers ( http://openopt.org/GLP ), especially I would recommend interalg ( http://openopt.org/interalg ), de and asa.