7.7 Zoutendijk’s Method of Feasible Directions 401
that is,
ε= −
δ
100
|f 1 |
f 1 ′
(7.45)
It is to be noted that the value ofεwill always be positive sincef 1 ′given in
Eq. (7.44) is always negative. This method yields good results if the percentage
reduction(δ)is restricted to small values on the order of 1 to 5.
7.7.3 Termination Criteria
In steps 4 and 5 of the algorithm, the optimization procedure is assumed to have
converged whenever the maximum value ofα(α∗) ecomes approximately zero andb
the results of the current iteration satisfy the relations stated in Eq. (7.32). In addition,
one can always test the Kuhn–Tucker necessary conditions before terminating the
procedure.
However, we can show that if the Kuhn–Tucker conditions are satisfied, the value
ofα∗will become zero. The Kuhn–Tucker conditions are given by
∇f+
∑p
j= 1
λj∇gj= 0 (7.46)
λj> 0 , = 1 , 2 ,... , p (7.47)
where the firstpconstraints are assumed to be the active constraints. Equation (7.46)
gives
ST∇ f =−
∑p
j= 1
λjST∇gj> 0 (7.48)
ifSis a usable feasible direction. Thus if the Kuhn–Tucker conditions are satisfied at
a pointXi, we will not be able to find any search directionSthat satisfies the strict
inequalities in the relations
ST∇gj≤ 0 , j= 1 , 2 ,... , p
ST∇f≤ 0 (7.49)
However, these relations can be satisfied with strict equality sign by taking the trivial
solutionS= 0 , which means that the value ofα∗in the direction-finding problem,
Eqs.(7.39), is zero. Some modifications and accelerating techniques have been sug-
gested to improve the convergence of the algorithm presented in this section and the
details can be found in Refs. [7.7] and [7.8].
Example 7.2
Minimizef (x 1 , x 2 )=x 12 +x 22 − 4 x 1 − 4 x 2 + 8
subjectto
g 1 (x 1 , x 2 )=x 1 + 2 x 2 − 4 ≤ 0
with the starting pointX 1 =
{ 0
0
}
.Takeε 1 = 0. 0 01,ε 2 = 0. 0 01, andε 3 = 0. 0 1.
