7.6 Basic Approach in the Methods of Feasible Directions 393
Table 7.2 Results for Example 7.1
Solution of the
Iteration New linearized approximating LP
number, constraint problem
i considered Xi+ 1 f (Xi+ 1 ) g 1 (Xi+ 1 )
1 − 2 ≤x 1 ≤2 and
− 2 ≤x 2 ≤ 2
(− 2. 0 , 2 .0) − 4 .00000 23.00000
2 − 16. 0 x 1 + 8. 0 x 2 − 25. 0 ≤ 0 (− 0. 56250 , 2 .00000) − 2. 56250 6.19922
3 − 7. 375 x 1 + 5. 125 x 2
− 8. 19922 ≤ 0
(0.27870, 2.00000) − 1. 72193 2.11978
4 − 2. 33157 x 1 + 3. 44386 x 2
− 4. 11958 ≤ 0
(− 0. 52970 , 0 .83759) − 1. 36730 1.43067
5 − 4. 85341 x 1 + 2. 73459 x 2
− 3. 43067 ≤ 0
(− 0. 05314 , 1 .16024) − 1. 21338 0.47793
6 − 2. 63930 x 1 + 2. 42675 x 2
− 2. 47792 ≤ 0
(0.42655, 1.48490) − 1. 05845 0.48419
7 − 0. 41071 x 1 + 2. 11690 x 2
− 2. 48420 ≤ 0
(0.17058, 1.20660) − 1. 03603 0.13154
8 − 1. 38975 x 1 + 2. 07205 x 2
− 2. 13155 ≤ 0
(0.01829, 1.04098) − 1. 02269 0.04656
9 − 1. 97223 x 1 + 2. 04538 x 2
− 2. 04657 ≤ 0
(− 0. 16626 , 0 .84027) − 1. 00653 0.06838
10 − 2. 67809 x 1 + 2. 01305 x 2
− 2. 06838 ≤ 0
(− 0. 07348 , 0 .92972) − 1. 00321 0.01723
7.6 Basic Approach in the Methods of Feasible Directions
In the methods of feasible directions, basically we choose a starting point satisfying all
the constraints and move to a better point according to the iterative scheme
Xi+ 1 =Xi+λSi (7.25)
whereXiis the starting point for theith iteration,Si the direction of movement,λ
thedistance of movement (step length), andXi+ 1 the final point obtained at the end
of theith iteration. The value ofλis always chosen so thatXi+ 1 lies in the feasible
region. The search directionSiis found such that (1) a small move in that direction
violatesno constraint, and (2) the value of the objective function can be reduced in
that direction. The new pointXi+ 1 is taken as the starting point for the next iteration
and the entire procedure is repeated several times until a point is obtained such that
no direction satisfying both properties 1 and 2 can be found. In general, such a point
denotes the constrained local minimum of the problem. This local minimum need not
be a global one unless the problem is a convex programming problem. A direction
satisfying property 1 is calledfeasiblewhile a direction satisfying both properties 1
and 2 is called ausable feasible direction. This is the reason that these methods are
