Engineering Optimization: Theory and Practice, Fourth Edition

406 Nonlinear Programming III: Constrained Optimization Techniques

IfXiis the starting point for theith iteration (at whichgj 1 , gj 2 ,... , gjpare critically

satisfied), we findSifrom Eq. (7.66) as

Si= −

Pi∇ f(Xi)

||Pi∇ f(Xi) ||

(7.67)

wherePiindicates the projection matrixPevaluatedat the pointXi. IfSi= 0 ,we start

fromXiand move along the directionSito find a new pointXi+ 1 according to the

familiar relation

Xi+ 1 =Xi+λiSi (7.68)

whereλiis the step length along the search directionSi. The computational details for

calculatingλiwill be considered later. However, ifSi= 0 ,we have from Eqs. (7.64)

and (7.63),

−∇f (Xi)=Nλ=λ 1 ∇gj 1 +λ 2 ∇gj 2 + · · · +λp∇gjp (7.69)

where

λ= −(NTN)−^1 NT∇ f(Xi) (7.70)

Equation (7.69) denotes that the negative of the gradient of the objective function is

given by a linear combination of the gradients of the active constraints atXi. Further, if

allλj, given by Eq. (7.63), are nonnegative, the Kuhn–Tucker conditions [Eqs. (7.46)

and(7.47) will be satisfied and hence the procedure can be terminated.

However, if someλj are negative andSi= 0 ,Eq. (7.69) indicates that some

constraint normals∇gj make an obtuse angle with−∇f atXi. This also means

that the constraintsgj, for whichλj are negative, are active atXibut should not be

considered in finding a new search directionSthat will be both feasible and usable. (If

we consider all of them, the search directionScomes out to be zero.) This is illustrated

in Fig. 7.9, where the constraint normal∇g 1 (Xi) hould not be considered in findings

a usable feasible directionSat pointXi.

In actual practice we do not discard all the active constraints for whichλj are

negative in forming the matrixN. Rather, we delete only one active constraint that

corresponds to the most negative value ofλj. That is, the newNmatrix is taken as

Nnew=[∇gj 1 ∇gj 2 · · · ∇gj q− 1 ∇gj q+ 1 ∇gj q+ 2 · · · ∇gjp] (7.71)

where∇gj qis dropped fromNby assuming thatλqis most negative amongλjobtained

from Eq. (7.63). The new projection matrix is formed, by dropping the constraint

gj q, as

Pnew=(I−Nnew(NTnewNnew)−^1 NTnew) (7.72)

and the new search direction(Si)newas

(Si)new= −

Pnew∇ f(Xi)

||Pnew∇ f(Xi) ||

(7.73)