Calculate by hand three iterations of the GoldenSection Sear

Calculate by hand three iterations of the Golden-Section Search algorithm to approximate the maximum of f(x) = -0.lx^2 - e^-x. Use an initial bracket of X_l = 0 and X_U = 3. Show work, and for each iteration indicate the value of X_opt.

Solution

Define an interval with a single answer (unique maximum) inside the range

sign of the curvature does not change in the given range

•Divide interval into 3 sections by adding two internal points between ends

•Evaluate the function at the two internal points x1 and x2

if f(x1) > f(x2)

the maximum is between xmn and x2

redefine range xmn = xmn, xmx = x2

if f(x1) < f(x2)

the maximum is between x1 and xmx

redefine range xmn = x1, xmx = xmx

Divide new smaller interval into 3 sections and start over

Set the following conditions:

(1) L = L1 + L2

(2) R = L/L2 = L2/L1

substitute (1) into (2) ==> 1 + R = 1/R

solve for R (R is called the Golden Ratio, named by ancient Greeks)

R = (sqrt(5)-1)/2 = .61803

So if the range is [0 , 1]

X1 = 1 - R = .38197

X2 = 0 + R = .61803

The ratio of the larger length to the smaller remains L2 / L1 = R = .61803

So in general, for the range is [xmn , xmx]

X1 = xmx - R * (xmx - xmn)

X2 = xmn + R * (xmx - xmn)

The maximum x distance between the current guess and the current range is called the error.

ERR = (1-R) * (xmx - xmn) is the maximum value =(1-.61803)*(3-0)=.38197*3= 1.14591 =xopt for first iteration

now ERR becomes xmin

ERR2=(1-R)*(xmx-xmin) =.3897*(3-1.14591) = .72253= xopt

now ERR2 becomes xmin

ERR3=(1-R)*(3-.72253) = .8875 =xopt after third iteration