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

william ratcliff wrote:

As for deprecation--is it really true that scipy.optimize.anneal is deprecated?

I think Dmitrey simply meant that no one has maintained it in a while, which is true. To answer your question, no one has claimed stewardship of anneal, so please suggest modifications as you think would help. We appreciate your contributions. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco

What I suggest is simply a slightly modified version of what's in anneal.pyto add the following: class simple_sa(base_schedule): def init(self, **options): self.__dict__.update(options) if self.m is None: self.m = 1.0 if self.n is None: self.n = 1.0 self.c = self.m * exp(-self.n * self.quench) def update_guess(self, x0): x0 = asarray(x0) T = self.T myFlag=True while myFlag: u = squeeze(random.uniform(0.0, 1.0, size=self.dims)) y = sign(u-0.5)*T*((1+1.0/T)**abs(2*u-1)-1.0) xc = y*(self.upper - self.lower) xt=x0+xc indu=where(xt>self.upper) # find where it goes above the upper bounds indl=where(xt<self.lower) # below the lower bounds if ((indu[0].size==0) & (indl[0].size==0)): myFlag=False #if it goes out of the box, try a new guess # restart xnew = xt return xnew def update_temp(self): self.T = self.T0*exp(-self.c * self.k**(self.quench)) self.k += 1 return This will keep solutions within specified upper and lower bounds. It does not sequentially choose parameters to vary. It simply asks, is my trial move valid? You can think of it as adding an infinite barrier at the walls. Then, one asks, if the trail move is not valid, then what do I do? The simplest solution is to stay where I am and to try again. It can still get stuck on the walls if the true solution is outside of the bounds. It should respect detailed balance. In anneal.py, if you have a glassy function, with a downturn near one of the walls, then it will still be able to explore outside of the specified bounds. There are some cases where you have information (for example, energies are positive) that allow you to constrain your search space and one should have the option of doing so. If the search gets stuck on the walls and the limits given were based on intuition rather than physical constraints, then one can simply expand the limits to see if it is a question of the constraints being too tight. Cheers, William On 4/25/07, dmitrey <openopt@ukr.net> wrote:

Check for the case: objFun(x) = sum(x) x0 = [0 0 0 0 0 0 0 0 0 1] (or very small numbers instead of zeros, smaller than typicalDeltaX/50 for example) lb = zeros ub = ones (or any other)

so if you use random shift for all coords (x = x_prev + deltaX, all coords of deltaX are random), the probability of "move" is 2^(-9)=1/512 and probability of "stay" is 1-2^(-9) = 511/512. this is valid for current update_guess() from anneal class fast_sa: def update_guess(self, x0): x0 = asarray(x0) u = squeeze(random.uniform(0.0, 1.0, size=self.dims)) T = self.T y = sign(u-0.5)*T*((1+1.0/T)**abs(2*u-1)-1.0) xc = y*(self.upper - self.lower) (so xc=deltaX change ALL coords) xnew = x0 + xc return xnew

class cauchy_sa(base_schedule): def update_guess(self, x0): x0 = asarray(x0) numbers = squeeze(random.uniform(-pi/2, pi/2, size=self.dims)) xc = self.learn_rate * self.T * tan(numbers) xnew = x0 + xc (ALSO modify ALL coords) return xnew

class boltzmann_sa(base_schedule): def update_guess(self, x0): std = minimum(sqrt(self.T)*ones(self.dims), (self.upper-self.lower)/3.0/self.learn_rate) x0 = asarray(x0) xc = squeeze(random.normal(0, 1.0, size=self.dims)) xnew = x0 + xc*std*self.learn_rate (ALSO modify ALL coords) return xnew

If you use random shift for 1 coord only (sequential) there can be other problems.

WBR, D.

william ratcliff wrote:

...

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

_______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-dev