[SciPy-Dev] optimize: add algorithm for global optimization basin hopping

josef.pktd@gmai... josef.pktd@gmai...
Wed Oct 10 14:38:10 CDT 2012


On Wed, Oct 10, 2012 at 3:24 PM,  <josef.pktd@gmail.com> wrote:
> 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
> optimization, 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.

just as additional motivation:

least trimmed squares:
It calculates least squares estimation on a subset of the observations
and treats the rest as outliers.
There can be a very large number of local optima, given by which
observations are included.

The best algorithm I have seen in the literature uses a few hundred
random starts, optimizes a few steps and then optimizes the 10 or 30
best to convergence.

Josef

>
> 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
>>


More information about the SciPy-Dev mailing list