Chapter 09.01 Golden Section Search Method

Chapter 09.01

Golden Section Search Method

After reading this chapter, you should be able to:

1.

2.

3.

4.

Understand the fundamentals of the Equal Interval Search method

Understand how the Golden Section Search method works

Learn about the Golden Ratio

Solve one-dimensional optimization problems using the Golden Section Search

method

Equal Interval Search Method

One of the simplest methods of finding the local maximum or local minimum is the Equal

Interval Search method. Let¡¯s restrict our discussion to finding the local maximum of f ( x )

where the interval in which the local maximum occurs is [a, b] . As shown in Figure 1, let¡¯s

choose an interval of ¦Å over which we assume the maximum occurs. Then we can compute

?a+b ¦Å ?

? a+b ¦Å ?

?a+b ¦Å ?

?a+b ¦Å ?

? ? . If f ?

+ ?¡Ý f?

? ? , then the interval in

f?

+ ? and f ?

2?

2?

2?

2?

? 2

? 2

? 2

? 2

?a + b ¦Å ?

? a+b ¦Å ?

which the maximum occurs is ?

? , b ? , otherwise it occurs in ?a,

+ ? . This

2 ?

2

2?

? 2

?

reduces the interval in which the local maximum occurs. This procedure can be repeated until

the interval is reduced to the level of our choice.

09.01.1

Golden Search Method

09.01.2

f(x)

M?

M

+

A

a

¦Å

¦Å

2

2

a+b

2

B

b

x

Figure 1A Equal interval search method (new upper bound can be identified).

Remarks:

As can be seen from the marked data points A, M ? , M + , and B on Figure 1A, the function

values have increased from point A to point M-, but then have decreased from point M ? to

point M + . Whenever there is a sudden change in the pattern, such as from increasing the

function value to decreasing its value, as shown in Figure 1A (or vice versa, as shown in

Figure 1B, where f L < f 2 < f1 and then f1 > f u ), then the new lower and upper bound

bracket values can be found. In this case, the new lower bound remains to be the same as its

previous lower bound (at point A), and the new upper bound can be found (at point M + ), as

shown in Figure 1A.

Figure 1B Equal interval search method (new lower bound can be identified).

Golden Search Method

09.01.3

Example 1

Consider Figure 2 below. The cross-sectional area A of a gutter with equal base and edge

length of 2 is given by

A = 4 sin ¦È (1 + cos ¦È )

Using an initial interval of [0, ¦Ð / 2] , find the interval after 3 iterations. Use an initial interval

¦Å = 0.2 .

2

¦È

2

2

¦È

Figure 2 Cross section of the gutter.

Solution

If we assume the initial interval to be [0, ¦Ð / 2] ? [0,1.5708] and choose ¦Å = 0.2 , then

?a+b ¦Å ?

? 0 + 1.5708 0.2 ?

f?

+ ?= f?

+

?

2?

2

2 ?

? 2

?

= f (0.88540 )

= 5.0568

?a+b ¦Å ?

? 0 + 1.5708 0.2 ?

f?

? ?= f?

?

?

2?

2

2 ?

? 2

?

= f (0.6854)

= 4.4921

Since f (0.88540 ) > f (0.68540 ) , the interval in which the local maximum occurs is

[0.68540,1.5708] .

Now

?a+b ¦Å ?

? 0.68540 + 1.5708 0.2 ?

f?

+ ?= f?

+

?

2?

2

2 ?

? 2

?

= f (1.2281)

= 5.0334

Golden Search Method

?a+b ¦Å ?

f?

? ?=

2?

? 2

=

09.01.4

? 0.68540 + 1.5708 0.2 ?

f?

?

?

2

2 ?

?

f (1.0281)

= 5.1942

Since f (1.2281) < f (1.0281) , the interval in which the local maximum occurs is

[0.68540,1.2281] .

Now

?a+b ¦Å ?

? 0.68540 + 1.2281 0.2 ?

f?

+ ?= f?

+

?

2?

2

2 ?

? 2

?

= f (1.0567 )

= 5.1957

?a+b ¦Å ?

? 0.68540 + 1.2281 0.2 ?

f?

? ?= f?

?

?

2?

2

2 ?

? 2

?

= f (0.8567 )

= 5.0025

Since f (1.0567 ) > f (0.8567 ) , then the interval in which the local maximum occurs is

(0.8567,1.2281) . After sixteen iterations, the interval is reduced to 0.02 and the

approximation of the maximum area is 5.1961 at an angle of 60.06 degrees.

The exact answer is ¦È = 1.0472 for which f (¦È ) = 5.1962 .

What is the Golden Section Search method used for and how does it work?

The Golden Section Search method is used to find the maximum or minimum of a unimodal

function. (A unimodal function contains only one minimum or maximum on the interval

[a,b].) To make the discussion of the method simpler, let us assume that we are trying to find

the maximum of a function. The previously introduced Equal Interval Search method is

somewhat inefficient because if the interval is a small number it can take a long time to find

the maximum of a function. To improve this efficiency, the Golden Section Search method is

suggested.

As shown in Figure 3, choose three points xl , x1 and xu ( xl < x1 < xu ) along the x-

axis with corresponding values of the function f ( xl ) , f ( x1 ) , and f ( xu ) , respectively. Since

f (x1 ) > f (xl ) and f (x1 ) > f (xu ) , the maximum must lie between xl and xu . Now a fourth

point denoted by x2 is chosen to be between the larger of the two intervals of [ xl , x1 ] and

[ x1 , xu ] . Assuming that the interval [ xl , x1 ] is larger than [ x1 , xu ] , we would chose [ xl , x1 ] as

the interval in which x2 is chosen. If f (x2 ) > f (x1 ) then the new three points would be

Golden Search Method

09.01.5

xl < x2 < x1 ; else if f (x2 ) < f (x1 ) then the new three points are x2 < x1 < xu . This process is

continued until the distance between the outer points is sufficiently small.

f (x 2 )

f (x )

f (xl )

f (x1)

f

(x )

u

x

x

x

l

2

x

1

x

u

Figure 3 Cross section of the gutter.

How are the intermediate points in the Golden Section Search determined?

We chose the first intermediate point xl to equalize the ratio of the lengths as shown in Eq.

(1) where a and b are distance as shown in Figure 4. Note that a + b is equal to the distance

between the lower and upper boundary points xl and xu .

a

b

=

(1)

a+b a

f (x )

f ( x1 )

f ( xl )

f ( xu )

x

xl

a

x1 b

xu

Figure 4 Determining the first intermediate point

The second intermediate point x2 is chosen similarly in the interval a to satisfy the

following ratio in Eq. (2) where the distances of a and b are shown in Figure 5.

b a ?b

=

a

b

(2)

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download