Engineering Optimization: Theory and Practice, Fourth Edition

312 Nonlinear Programming II: Unconstrained Optimization Techniques

6.2.2 Random Walk Method

Therandom walk methodis based on generating a sequence of improved approxima-

tions to the minimum, each derived from the preceding approximation. Thus ifXiis

the approximation to the minimum obtained in the(i− 1 )th stage (or step or iteration),

the new or improved approximation in theith stage is found from the relation

Xi+ 1 =Xi+λui (6.18)

whereλis a prescribed scalar step length anduiis a unit random vector generated in the

ithstage. The detailed procedure of this method is given by the following steps [6.3]:

1.Start with an initial pointX 1 , a sufficiently large initial step lengthλ,a minimum

allowable step lengthε, and a maximum permissible number of iterationsN.

2.Find the function valuef 1 = f(X 1 ).

3 .Set the iteration number asi=1.

4.Generate a set ofnrandom numbersr 1 , r 2 ,... , rneach lying in the interval

[− 1 , 1] and formulate the unit vectoruas

u=

1

(r^21 +r 22 + · · · +rn^2 )^1 /^2











r 1

r 2

..

.

rn











(6.19)

The directions generated using Eq. (6.19) are expected to have a bias toward

the diagonals of the unit hypercube [6.3]. To avoid such a bias, the length

of the vector,R, is computed as

R=(r^21 +r 22 + · · · +rn^2 )^1 /^2

and the random numbers generated(r 1 , r 2 ,... , rn) re accepted only ifa R≤ 1

but are discarded ifR>1. If the random numbers are accepted, the unbiased

random vectoruiis given by Eq. (6.19).

5 .Compute the new vector and the corresponding function value asX=X 1 +λu

andf=f (X).

6.Compare the values offandf 1. If f< f 1 , set the new values asX 1 = Xand

f 1 = fand go to step 3. Iff≥f 1 , go to step 7.

7 .Ifi≤N, set the new iteration number asi=i+1 and go to step 4. On the

other hand, ifi>N, go to step 8.

8.Compute the new, reduced, step length asλ=λ/2. If the new step length is

smaller than or equal toε, go to step 9. Otherwise (i.e., if the new step length

is greater thanε), go to step 4.

9.Stop the procedure by takingXopt≈X 1 andfopt≈f 1.

This method is illustrated with the following example.

Example 6.3 Minimizef (x 1 , x 2 )=x 1 −x 2 + 2 x^21 + 2 x 1 x 2 +x 22 using random walk

method from the pointX 1 =

{ 0. 0

0. 0

}

with a starting step length ofλ= 1 .0. Takeε= 0. 05

andN=100.