Introduction to Optimization - Numerical Methods in Engineering with MATLAB - page 385

f ( x )

2 Rh - h

f 1

f 2

Rh

Rh

x

a x 1 x 2 b

h

(a)

Figure 10.2. Golden section telescoping.

f ( x )

Rh'

Rh'

x

x 1 x 2

a b

h'

(b)

Assuming that f 1 > f 2 , we set a ← x 1 and x 1 ← x 2 , which yields anewinterval( a , b )of

length h =

Rh , as illustrated inFig. 10.2(b). To carry out the next telescoping operation
weevaluate the functionat x 2 =

Rh and repeat the process.
The procedure works onlyif Figs.10.1(a) and (b) aresimilar; i.e., if the same
constant R locates x 1 and x 2 in both figures.Referring to Fig. 10.2(a), we note that
x 2 −

a +

h − Rh .Equating x 1 = 2 Rh − h . The same distance in Fig. 10.2(b) is x 1 − a =

the two, we get

h − Rh 2 Rh − h =

Substituting h = Rh and cancelling h yields

2 R − 1 = R (1 − R )

the solution of which is the golden ratio 21 :

+ √ 5
2

−

1

R = = 0 . 618 033 989 ... (10.3)

Note thateach telescoping decreases the intervalcontaining the minimumby the
factor R , which is not as goodas the factor of 0 5inbisection. However, the golden

search methodachieves this reductionwith one function evaluation , whereastwo
evaluations wouldbe neededinbisection.
The number of telescopings required to reduce h from

.

| b − a | to an error tolerance

ε is givenby

R n

| b − a | = ε

21

R is the ratioofthesides of a“goldenrectangle,” consideredbyancientGreeks to have the perfect
proportions.