A primal-dual affine scaling algorithm with necessary centering as
a safeguard
Jie Sun, Jishan Zhu, and Zhao Gong Yun
An interior point algorithm for linear programming is proposed and
analysed. At each iteration, this algorithm finds a point in a wide
neighborhood along a primal-dual affine scaling direction and it adds
a centering step only if the step along the affine scaling direction
is too short. Moreover, the centering direction is computed with
the old projection matrix which was obtained in the computation of
the affine scaling direction. The best complexity upper bound to date
is achieved by this algorithm.
Technical Report No. 647, Department of Mathematics,
National University of Singapore.
Published in Optimization 35 (1995), pp. 333-343.