When to stop a simulate annealing when it doesn't stop by itself

[alecrimi]

Hi guys
I posted something similar some time ago:
This is a long story, I make it short:
I am working in a project where I need to find a matrix defined by a third degree polynomial.
Originally I thought that a good idea can be to find the solution iteratively using a gradient descent technique, so I implemented a golden section line search in MATLAB (with the code described below).
The algorithm looks powerful (it finds automatically the perfect step), but unfortunately the golden section line search does not avoid being stuck in local minima.
So I moved to a stochastic approach like simulated annealing, now the problem is that with my objective function the default convergence never happens.
So I have to force annealing to stop. BUT WHEN ?
I tried after some iteration but the annealing has the defect that at some point it randomize his trusted region and maybe when I stop it, it is really far from the minima (I am using too many iterations). And I have the same problem with time limit. So when I should stop the minima the search ?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Code using the golden section:

%Initial third degree polynomial
Cest = initial_guess;
normdev=inf ;
stepsize=inf;

%Stopping condition
stopping_condition = 10^(-5) *norm(X*X'/no_samples,'fro');

while abs(normdev*stepsize) > stopping_condition
%Third degree polynomial
dnew = Cest - 1/no_samples*(X*X' - 2/sigma^2 * (Cest*Cest'*Cest-Cest*B'*Cest));
%Find the best stepsize as a minimum using the goldensection line search
stepsize = fminbnd( @(stepsize) step(stepsize,Cest,dnew,X*X',B,sigma,no_samples),-.1,.1);

%Update
Cest = Cest + stepsize*dnew;
normdev = norm(dnew,'fro');
end

function error = step(stepsize,Cest,dnew,XX,B,sigma,no_samples)
Cest = Cest + stepsize*dnew;
error = norm(Cest - 1/no_samples*(XX - 2/sigma^2 * (Cest^3-Cest*B*Cest)),'fro');

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Code using the simulated annealing:
Cest = initial_point;

lb = -20*ones(size(Cest));
ub = 20*ones(size(Cest));

options = saoptimset('MaxIter',300) ;

Cest = simulannealbnd(@(funcobj) myfuncobj(Cest ,X*X',B,sigma,no_samples),Cest,lb,ub, options);


function error = myfuncobj( Cest, XX, B, sigma, no_samples)
error = norm(Cest - 1/no_samples*(XX - 2/sigma^2 * (Cest^3-Cest*B*Cest)),'fro');

 

[flat man]

Have you considered using code from a book or published paper?

 

[alecrimi]

Hi
Thank you for your reply.
Unfortunately... I can't
Have you seen my target matrix ? Does it look like anything you can find in a book or was already published ?

The expression for a gradient descent works (but it is stuck in a local minimum).
I guess it will be solved with a stochastic approach, but reading all the tutorial, they assume explicit functions as error function, I haven't seen anything like I need to minimize.

 

[flat man]

Why can't you use code from a book?

Also, if you want me to look at your objective function, you should write it down and clearly label all its variables.

 

[blue_raver22]

As a scientist, my response would be to carefully evaluate the convergence of the simulated annealing algorithm before considering stopping it manually. This could involve analyzing the behavior of the objective function over multiple runs, and determining if it is consistently reaching a certain value or if it is fluctuating. Additionally, it may be helpful to plot the trajectory of the algorithm to visually see if it is getting closer to the global minimum or if it is stuck in a local minimum.

If it is determined that the algorithm is not converging, there are a few potential options for stopping it manually. One option could be to set a maximum number of iterations or a time limit, as mentioned in the post. However, this may not always be reliable as the algorithm may still be far from the global minimum when it reaches these limits.

Another option could be to monitor the temperature and energy of the system during the annealing process. If the temperature remains high and the energy does not decrease significantly, it may be an indication that the algorithm is stuck and may benefit from being stopped.

Overall, it is important to carefully evaluate the behavior of the algorithm and consider the potential consequences of stopping it manually before making a decision. It may also be helpful to consult with other experts or colleagues for their insights and advice.