
Interior Point Methods 237
and
δ
z
= max(−1.5 ∗ min{z
i
}, 0),
and then form the quantities
δ
x
= δ
x
+ [(x + δ
x
e)
T
(z + δ
z
e)]/[2
n
P
i=1
(z
i
+ δ
z
)]
and
δ
z
= δ
x
+ [(x + δ
x
e)
T
(z + δ
z
e)]/[2
n
P
i=1
(x
i
+ δ
x
)].
Then, the initial point is x
(0)
i
= x
i
+ δ
x
and z
(0)
i
= z
i
+ δ
z
for i = 1, ..., n
and π
(0)
= π.
By construction of δ
x
and δ
z
the initial point generated in this manner
will be such that x
(0)
≥ 0 and z
(0)
≥ 0. Furthermore, if δ
x
and δ
z
are positive,
then x
(0)
> 0 and z
(0)
> 0; see Exercise 6.6.
Example 6.4
Consider the linear program
minimize −3x
1
− 2x
2
subject to x
1
+2x
2
+ x
3
= 20
2x
1
+2x
2
+x
4
= 15
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
We show an iteration of the predictor-corrector primal-dual interior poin ...