Minimize a function using simulated annealing algorithm

Good afternoon, I need your help.

I've been struggling to get this working, I'm trying to get this function:

function f = myf(x)

mycoef = [1 5 -2 5 7]';

z = [cos(x), cos(1.6*x) cos(2*x), cos(4.5*x), cos(9*x)];

f = z * mycoef;

optimized using the simulated annealing algorithm, the problem is that I'm getting a lot of errors from matlab, Could you help me get this done?

Thank you very much

Answer 1

[William Rose]

@Álvaro Recalde, Simulated annealing is best suited to combinatorial minimization problems. Simulated annealing can also be applied to problems like yours, in which the adjutable parameters are continuous. My advice is to use fmincon() to minimize your function.

You said you are trying to "optimize" myf(x). Do you want to minimize it or maximize it? Are you holding mycoef constant, and varying x? YOu can solve this 1D problem with relatively simple calculus. Or are you adjusting mycoef as well as x? If so, you must put contraints on the allowed values for the coefficients, because it you don't, then setting coefficients equal to +Inf or -Inf will be a "solution" which you don't want.

Did you notice that myf(x) is periodic, with period 20*pi? In other words, mf(x)=myf(x+20*pi). Therefore, if you are varying x, you should restrict it to [0,20*pi), to avoid duplicate solutions.

[William Rose]

@Álvaro Recalde,

There is a discussion of simulated annealing which I have found very helpful, in Numerical Recipes, Third edition, section 10.12, pp. 549-545. The authors describe how to apply simulated annealing to combinatorial and continuous minimization problems. The authors explain that it is more complicated to apply simulated annealing to continuous problems - which yours is.

Good luck with your work.

[Sam Chak]

Hi @Álvaro Recalde

Like @William Rose said, it is periodic.

[William Rose]

@Álvaro Recalde, I am realizing why this could be a nice demonstration problem for the potential power of simulated annealing. myf(x) has many local minima (and many loca maxma) in one period, i.e. in x=[0,20*pi). Therefore, if you use calculus, there will be many values of x for which the first derivative equals zero. Finding the "global" minimum is non-trivial.

YOu can use fincon by startng from many points, and choosing the solution that gives the lowest minimum. This gets somewhat complicated in multiple dimensions, but in this one-dimensional problem it is relatively easy. I have provided example code to do this in an answer to another question.

[William Rose]

@Álvaro Recalde,

See here for where I provide code to start fmincon() from 81 starting points in a 4-dimensional search space, and then pick out the best solution obtained from all 81 tries.

[William Rose]

@Álvaro Recalde,

%minimize1DMultistart.m   W. Rose 20220523
% Find the global minimum of a function with many local minima.
% Function myf(x) is periodic with period 20*pi.  It has many local minima.
% Find the global minimum by calling fmincon() 20 times.  
% Use a different x0 as the start point, each time.
% Then find the overall best minimum point.
% Display results on console and graphically.

x0=((0:19)+.5)*pi;          %vector of starting points
x  =zeros(length(x0),1);    %vector for best x from each trial
xmin=0; xmax=20*pi;
sse=zeros(length(x0),1);    %vector for sum squared error from each trial
for i=1:length(x0)
    [x(i),sse(i)]=fmincon(@myf,x0(i),[],[],[],[],xmin,xmax);
end

Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.


Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

%% Find the best solution among the 20 tries, and display results.
[ssebest,ibest]=min(sse);
fprintf('Best (lowest) value=%.3f\n',ssebest)

Best (lowest) value=-14.677

fprintf('Best x-value: %.3f\n',x(ibest))

Best x-value: 40.888

xplot=(0:.01:20)'*pi;
figure; plot(xplot,myf(xplot),'-k',x(ibest),ssebest,'r*')

%% Define function to be minimized
function f = myf(x)
mycoef = [1 5 -2 5 7]';
z = [cos(x), cos(1.6*x) cos(2*x), cos(4.5*x), cos(9*x)];
f = z * mycoef;
end

Try the above. The script calls the minimization routine fmincon() 20 times, with a differnet initial guess each time. The initial guesses are 20 evenly-spaced x-values across one cycle of the function myf(). fmincon() finds the best minimum it can find, from each start point. After all 20 minimizations, the script identifies and displays the overall best minimum value that it found.