Page 348 - Applied Numerical Methods Using MATLAB

UNCONSTRAINED OPTIMIZATION 337

function [xo,fo] = sim_anl(f,x0,l,u,kmax,q,TolFun)
% simulated annealing method to minimize f(x) s.t. l <= x <= u
N = length(x0);
x = x0; fx = feval(f,x);
xo=x;fo=fx;
if nargin < 7, TolFun = 1e-8; end
if nargin < 6, q = 1; end %quenching factor
if nargin < 5, kmax = 100; end %maximum iteration number
for k = 0:kmax
Ti = (k/kmax)^q; %inverse of temperature from 0 to 1
mu = 10^(Ti*100); % Eq.(7.1.23)
dx = mu_inv(2*rand(size(x))- 1,mu).*(u - l);
x1=x+dx; %next guess
x1 = (x1 < l).*l +(l <= x1).*(x1 <= u).*x1 +(u < x1).*u;
%confine it inside the admissible region bounded by l and u.
fx1 = feval(f,x1); df = fx1- fx;
if df < 0|rand < exp(-Ti*df/(abs(fx) + eps)/TolFun) Eq.(7.1.24)
x = x1; fx = fx1;
end
if fx < fo, xo = x; fo = fx1; end
end
function x = mu_inv(y,mu) % inverse of mu-law Eq.(7.1.22)
x = (((1+mu).^abs(y)- 1)/mu).*sign(y);
%nm717 to minimize an objective function f(x) by various methods.
clear, clf
f = inline(’x(1)^4 - 16*x(1)^2 - 5*x(1) + x(2)^4 - 16*x(2)^2 - 5*x(2)’,’x’);
l=[-5 -5];u=[5 5]; %lower/upperbound
x0=[00]
[xo_nd,fo] = opt_Nelder(f,x0)
[xos,fos] = fminsearch(f,x0) %cross-check by MATLAB built-in routines
[xou,fou] = fminunc(f,x0)
kmax=500;q=1; TolFun = 1e-9;
[xo_sa,fo_sa] = sim_anl(f,x0,l,u,kmax,q,TolFun)

which remains as big as e −1 for | f/f (x)|= ε f at the last iteration k = k max ,
meaning that the probability of taking a step hopefully to escape from a local
minimum and find the global minimum at the risk of increasing the value of
objective function by the amount f =|f(x)|ε f is still that high. The shapes of
the two functions related to the temperature are depicted in Fig. 7.7.
We make the MATLAB program “nm717.m”, which uses the routine “sim_
anl()” to minimize a function

4 2 4 2
f(x) = x − 16x − 5x 1 + x − 16x − 5x 2 (7.1.25)
2
2
1
1
and tries other routines such as “opt_Nelder()”, “fminsearch()”, and “fmi-
nunc()” for cross-checking. The results of running the program are summa-
rized in Table 7.1, which shows that the routine “sim_anl()” may give us the
global minimum even when some other routines fail to find it. But, even this
routine based on the idea of simulated annealing cannot always succeed and its
success/failure depends partially on the initial guess and partially on luck, while
the success/failure of the other routines depends solely on the initial guess.