Engineering Optimization: Theory and Practice, Fourth Edition

330 Nonlinear Programming II: Unconstrained Optimization Techniques

X 0 is the centroid of all the pointsXiexcepti=h:

X 0 =

1

n

n∑+ 1

i= 1

i

=h

Xi (6.50)

andα>0 is the reflection coefficient defined as

α=

distance betweenXrandX 0

distance betweenXhandX 0

(6.51)

ThusXrwill lie on the line joiningXhandX 0 , on the far side ofX 0 fromXhwith

|Xr−X 0 | =α|Xh−X 0 | If. f (Xr) ies betweenl f (Xh) nda f (Xl) where, Xl is the

vertex corresponding to the minimum function value,

f (Xl) = min

i = 1 ton+ 1

f (Xi) (6.52)

Xhis replaced byXrand a new simplex is started.

If we use only the reflection process for finding the minimum, we may encounter

certain difficulties in some cases. For example, if one of the simplexes (triangles in

two dimensions) straddles a valley as shown in Fig. 6.12 and if the reflected pointXr

happens to have an objective function value equal to that of the pointXh, we will

enter into a closed cycle of operations. Thus ifX 2 is the worst point in the simplex

defined by the verticesX 1 ,X 2 , andX 3 , the reflection process gives the new simplex

with verticesX 1 ,X 3 , andXr. Again, sinceXrhas the highest function value out of

the verticesX 1 ,X 3 , andXr, we obtain the old simplex itself by using the reflection

process. Thus the optimization process is stranded over the valley and there is no way

of moving toward the optimum point. This trouble can be overcome by making a rule

that no return can be made to points that have just been left.

Figure 6.12 Reflection process not leading to a new simplex.