Page 333 - Applied Numerical Methods Using MATLAB

322 OPTIMIZATION
program “nm711.m”, which uses this routine to find the minimum point of the
objective function
2
2
f(x) = (x − 4) /8 − 1 (7.1.1)
GOLDEN SEARCH PROCEDURE

Step 1. Pick up the two points c = a + (1 − r)h and d = a + rh inside the
√
interval [a, b], where r = ( 5 − 1)/2and h = b − a.
Step 2. If the values of f(x) at the two points are almost equal [i.e., f(a) ≈
f(b)] and the width of the interval is sufficiently small (i.e., h ≈ 0),
o
o
then stop the iteration to exit the loop and declare x = c or x = d
depending on whether f(c) < f (d) or not.Otherwise,gotoStep3.
Step 3.If f(c) < f (d), let the new upper bound of the interval b ← d;oth-
erwise, let the new lower bound of the interval a ← c. Then, go to
Step 1.

function [xo,fo] = opt_gs(f,a,b,r,TolX,TolFun,k)
h=b-a;rh= r*h;c=b-rh;d=a+rh;
fc = feval(f,c); fd = feval(f,d);
ifk<=0 | (abs(h) < TolX & abs(fc - fd) < TolFun)
if fc <= fd, xo = c; fo = fc;
else xo = d; fo = fd;
end
if k == 0, fprintf(’Just the best in given # of iterations’), end
else
if fc < fd, [xo,fo] = opt_gs(f,a,d,r,TolX,TolFun,k - 1);
else [xo,fo] = opt_gs(f,c,b,r,TolX,TolFun,k - 1);
end
end
%nm711.m to perform the golden search method
f711 = inline(’(x.*x-4).^2/8-1’,’x’);
a=0;b=3;r =(sqrt(5)-1)/2; TolX = 1e-4; TolFun = 1e-4; MaxIter = 100;
[xo,fo] = opt_gs(f711,a,b,r,TolX,TolFun,MaxIter)

Figure 7.1 shows how the routine “opt_gs()” proceeds toward the minimum
point step by step.
Note the following points about the golden search procedure.

ž At every iteration, the new interval width is
b − c = b − (a + (1 − r)(b − a)) = rh or d − a = a + rh − a = rh
(7.1.2)
so that it becomes r times the old interval width (b − a = h).