7.7 Zoutendijk’s Method of Feasible Directions 397s 1∂g 2
∂x 1+s 2∂g 2
∂x 2+ · · · +sn∂g 2
∂xn+θ 2 α≤ 0..
.s 1∂gp
∂x 1+s 2∂gp
∂x 2+ · · · +sn∂gp
∂xn+θpα≤ 0 (7.39)s 1∂f
∂x 1+s 2∂f
∂x 2+ · · · +sn∂f
∂xn+α≤ 0s 1 − 1 ≤ 0s 2 − 1 ≤ 0
..
.
sn− 1 ≤ 0
− 1 −s 1 ≤ 0− 1 −s 2 ≤ 0
..
.
− 1 −sn≤ 0wherepis the number of active constraints and the partial derivatives∂g 1 /∂x 1 , ∂g 1 /∂x 2 ,
... , ∂gp/∂xn, ∂f/∂x 1 ,... , ∂f/∂xnhave been evaluated at pointXi. Since the com-
ponents of the search direction,si, i= 1 ton, can take any value between−1 and 1,
we define new variablestiasti=si+ , 1 i=1 ton, so that the variables will always
be nonnegative. With this change of variables, the problem above can be restated as
a standard linear programming problem as follows:
Find(t 1 , t 2 ,... , tn, α, y 1 , y 2 ,... , yp+n+ 1 ) hichwminimizes −α
subject to
t 1∂g 1
∂x 1+t 2∂g 1
∂x 2+ · · · +tn∂g 1
∂xn+θ 1 α+y 1 =∑ni= 1∂g 1
∂xit 1∂g 2
∂x 1+t 2∂g 2
∂x 2+ · · · +tn∂g 2
∂xn+θ 2 α+y 2 =∑ni= 1∂g 2
∂xi..
.t 1∂gp
∂x 1+t 2∂gp
∂x 2+ · · · +tn∂gp
∂xn+θpα+yp=∑ni= 1∂gp
∂xi