The 'simple' way applies only to the anneal algorithm in scipy. When one chooses steps in a simulated annealing algorithm, there is always the question of how to step from the current point. For anneal, it is currently done based on an upper bound and lower bound (in one option). However, there is nothing to prevent the searcher from crawling its way out of the box. When most people imagine themselves searching in a bounded parameter space, that is not the expected behavior. Now, it is possible that the optimum solution is truly outside of the box and that the searcher is doing the right thing. However, if that is not the case, then there is a problem. So, what is one to do? The first obvious thing to try is to say, if you reach the edge of a bounded parameter, stay there. However, that is not ideal as you get stuck and can't explore the rest of the phase space. So, I use the simple heuristic that if a trial move is to take you outside of the box, simply stay where you are. In the next cycle, try to move again. This will keep you in the box, and if there is truly a solution outside of the box, will still move you towards the walls and let you know that maybe you've set your bounds improperly. Now, there are questions of efficiency. For example, how easy is it to get out of corners? Should one do reflections? However, I believe that my rather simple heuristic will preserve detailed balance and results in an algorithm that has the expected behavior and is better than having no option ;> As for deprecation--is it really true that scipy.optimize.anneal is deprecated? As for issues of this global optimizer or that global optimizer, why not let the user decide based on their expectations of their fitting surface? For some truly glassy surfaces, one is forced into techniques like simulated annealing, parrallel tempering, genetic algorithms, etc. and I imagine that their relative performance is based strongly on the particular problem that their are trying to solve. Cheers, WIlliam Ratcliff On 4/25/07, dmitrey <openopt@ukr.net> wrote:
Hallo! I have been accepted for participating in the GSoC program with project related to scipy and optimization. If noone else here is able or have no time, I would take a look (however, I can't spend much time before summer start because of my exams; and anneal (as well as other global solvers) is not my specialty).
I think that lb-ub bounds can hardly be implemented in a simple way because it depends very much on rand points generator quality, and the latter should be much more better than simple lb+rand*(ub-lb) elseware all points will be located in a thin area near their average value (same problem is present in integration of functions f: R^n->R with high dimensions (n>>1) ). I took a look at the generators by Joachim Vandekerckhove in his anneal (connected to my openopt for MATLAB/Octave), they seems to be too primitive. BTW afaik anneal currenlty is concerned as deprecated (I don't know better English word, not "up-to-date", old one), there are better global solvers, for example GRASP-based. WBR, D.
william ratcliff wrote:
say, who's responsible for the anneal portion of optimize? I'd like to check in a minor tweak which implements simple upper and bounds on the fit parameters.
Thanks, William
On 4/18/07, *Matthieu Brucher* <matthieu.brucher@gmail.com <mailto:matthieu.brucher@gmail.com>> wrote:
Hi,
I'm lauching a new thread, the last was pretty big, and as I almost put every advice in this proposal, I thought it would be better. First, I used scipy coding standard, I hope I didn't forget something.
I do not know where it would be put at the moment on my scipy tree, and the tests are visual for the moment, I have to make them automatic, but I do not know the framework used by scipy, I have to check it first.
So, the proposal : - combining several objects to make an optimizer - a function should be an object defining the __call__ method and graient, hessian, ... if needed. It can be passed as several separate functions as Alan suggested it, a new object is then created - an optimizer is a combination of a function, a step_kind, a line_search, a criterion and a starting point x0. - the result of the optimization is return after a call to the optimize() method - every object (step or line_search) saves its modification in a state variable in the optimizer. This variable can be accessed if needed after the optimization. - after each iteration, a record function is called with this state variable - it is a dict, BTW -, if you want to save the whole dict, don't forget to copy it, as it is modified during the optimization
For the moment are implemented : - a standard algorithm, only calls step_kind then line_search for a new candidate - the next optimizer would be one that calls a modifying function on the computed result, that can be useful in some cases - - criteria : - monotony criterion : the cost is decreasing - a factor can be used to allow an error - - relative value criterion : the relative value error is higher than a fixed error - absolute value criterion : the same with the absolute error - step : - gradient step - Newton step - Fletcher-Reeves conjugate gradient step - other conjugate gradient will be available - - line search : - no line search, just take the step - damped search, it's an inexact line search, that searches in the step direction a set of parameters than decreases the cost by dividing by two the step size while the cost is not decreasing - Golden section search - Fibonacci search
I'm not pulling other criterion, step or line search, as my time is finite when doing a structural change.
There are 3 classic optimization test functions in the package, Rosenbrock, Powell and a quadratic function, feel free to try them. Sometimes, the optimizer converges to the true minimum, sometimes it does not, I tried to propose several solutions to show that every combinaison does not manage to find the minimum.
Matthieu
_______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org <mailto:Scipy-dev@scipy.org> http://projects.scipy.org/mailman/listinfo/scipy-dev
------------------------------------------------------------------------
_______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-dev
_______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-dev