Engineering Optimization: Theory and Practice, Fourth Edition

328 Nonlinear Programming II: Unconstrained Optimization Techniques

If we do not recognizeX 5 as the optimum point at this stage, we proceed to

minimizefalong the directionS 2 =

{ 0

1

}

fromX 5. Then we would obtain

f 5 =f(X 5 ) =− 1. 25 , f+= f(X 5 +εS 2 )>f 5 ,

and f−= f(X 5 −εS 2 )>f 5

This shows thatf cannot be minimized alongS 2 , and henceX 5 will be the optimum

point. In this example the convergence has been achieved in the second cycle itself.

This is to be expected in this case, asfis a quadratic function, and the method is a

quadratically convergent method.

6.7 Simplex Method

Definition: Simplex. The geometric figure formed by a set ofn+1 points in an

n-dimensional space is called asimplex. When the points are equidistant, the simplex

is said to beregular. Thus in two dimensions, the simplex is a triangle, and in three

dimensions, it is a tetrahedron.

The basic idea in the simplex method†is to compare the values of the objective

function at then+1 vertices of a general simplex and move the simplex gradu-

ally toward the optimum point during the iterative process. The following equations

can be used to generate the vertices of a regular simplex (equilateral triangle in

two-dimensional space) of sizeain then-dimensional space [6.10]:

Xi=X 0 +pui+

∑n

j = 1 ,j

=i

quj, i= 1 , 2 ,... , n (6.46)

where

p=

a

n

√

2

(

√

n+ 1 +n− 1 ) and q=

a

n

√

2

(

√

n+ 1 − 1 ) (6.47)

whereX 0 is the initial base point andujis the unit vector along thejth coordinate axis.

This method was originally given by Spendley, Hext, and Himsworth [6.10] and was

developed later by Nelder and Mead [6.11]. The movement of the simplex is achieved

by using three operations, known as reflection, contraction, and expansion.

6.7.1 Reflection

IfXhis the vertex corresponding to the highest value of the objective function among

the vertices of a simplex, we can expect the pointXrobtained by reflecting the point

Xhin the opposite face to have the smallest value. If this is the case, we can construct

anew simplex by rejecting the pointXhfrom the simplex and including the new point

Xr. This process is illustrated in Fig. 6.10. In Fig. 6.10a,the pointsX 1 ,X 2 , andX 3

form the original simplex, and the pointsX 1 ,X 2 , andXrform the new one. Similarly,

in Fig. 6.10b, the original simplex is given by pointsX 1 ,X 2 ,X 3 , andX 4 , and the new

one byX 1 ,X 2 ,X 3 , andXr. Again we can construct a new simplex from the present one

†This simplex method should not be confused with the simplex method of linear programming.