Engineering Optimization: Theory and Practice, Fourth Edition

272 Nonlinear Programming I: One-Dimensional Minimization Methods

Table 5.3 Final Intervals of Uncertainty

Method Formula n= 5 n= 10

Exhaustive search Ln=

2

n+ 1

L 0 0. 33333 L 0 0. 18182 L 0

Dichotomous search
(δ= 0.01 and
n=even)

Ln=

L 0

2 n/^2

+δ

(

1 −

1

2 n/^2

)

1

4 L^0 +^0 .0075 with

n= 4 ,^18 L 0 + 0. 00875

withn= 6

0. 03125 L 0 + 0. 0096875

Interval halving (n≥ 3
and odd)

Ln=(^12 )(n−^1 )/^2 L 0 0. 25 L 0 0. 0625 L 0 withn= 9 ,

0. 03125 L 0 with

n= 11

Fibonacci Ln=
1
Fn

L 0 0. 125 L 0 0. 01124 L 0

Golden section Ln=(0.618)n−^1 L 0 0. 1459 L 0 0. 01315 L 0

Table 5.4 Number of Experiments for a Specified Accuracy

Method Error:

1

2

Ln

L 0

≤ 0. 1 Error:

1

2

Ln

L 0

≤ 0. 01

Exhaustive search n≥ 9 n≥ 99

Dichotomous search (δ= 0. 01 , L 0 =1) n≥ 6 n≥ 14

Interval halving (n≥3 and odd) n≥ 7 n≥ 13

Fibonacci n≥ 4 n≥ 9

Golden section n≥ 5 n≥ 10

is to findλ∗, the smallest nonnegative value ofλ,for which the function

f (λ)=f (X+λS) (5.27)

attains a local minimum. Hence if the original functionf(X) is expressible as an explicit

function ofxi(i = 1 , 2 ,... , n), we can readily write the expression forf (λ)=f(X

+λS) for any specified vectorS, set

df

dλ

(λ)= 0 (5.28)

and solve Eq. (5.28) to findλ∗ in terms ofXandS. However, in many practical

problems, the functionf (λ)cannot be expressed explicitly in terms ofλ(as shown in

Example 5.1). In such cases the interpolation methods can be used to find the value

ofλ∗.

Example 5.9 Derive the one-dimensional minimization problem for the following

case:

Minimizef (X)=(x^21 −x 2 )^2 +( 1 −x 1 )^2 (E 1 )

from the starting pointX 1 =

{− 2

− 2

}

along the search directionS=

{ 1 0. 0

0. 25

}

.