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.