Constrained Optimization Zoutendijik's method

Zoutendijk’s method of feasible directions

Algorithm is given in SS Rao book at page number 361
1. Start with an initial feasible point X1 and small numbers 𝜀1, 𝜀2, and 𝜀3 to test
the convergence of the method. Evaluate f (X1) and gj(X1), j = 1, 2, . . . , m. Set
the iteration number as i = 1.
2. If gj(Xi)<0, j = 1, 2, . . . , m (i.e. Xi is an interior feasible point), set the current
search direction as
Si = −∇f (Xi)
Normalize Si in a suitable manner and go to step 5. If at least one gj(Xi) = 0,
go to step 3.
3. Find a usable feasible direction S by solving the direction-finding problem:
Minimize − 𝛼
subject to
ST∇gj(Xi) + 𝜃j𝛼 ≤ 0, j = 1, 2, . . . , p
ST∇f + 𝛼 ≤ 0
−1 ≤ si
≤ 1, i = 1, 2, . . . , n
where si is the ith component of S, the first p constraints have been assumed to
be active at the point Xi (the constraints can always be renumbered to satisfy
this requirement), and the values of all 𝜃j can be taken as unity. Here 𝛼 can be
taken as an additional design variable.
4. If the value of 𝛼* found in step 3 is very nearly equal to zero, that is, if 𝛼* ≤𝜀1,
terminate the computation by taking Xopt ≃Xi. If 𝛼* >𝜀1, go to step 5 by taking
Si = S.
5. Find a suitable step length 𝜆i along the direction Si and obtain a new point Xi+1
as
Xi+1 = Xi + 𝜆iSi
The methods of finding the step length 𝜆i will be considered later.
6. Evaluate the objective function f (Xi+1).
7. Test for the convergence of the method. If
||||(f (Xi) − f (Xi+1))/f (Xi)|||| ≤ 𝜀2 and ‖Xi − Xi+1‖ ≤ 𝜀3
terminate the iteration by taking Xopt ≃Xi+1. Otherwise, go to step 8.
8. Set the new iteration number as i = i+1, and repeat from step 2 onward.