A note on Mascarenhas' counter example about global convergence of the affine scaling algorithm

Tamas Terlaky and Takashi Tsuchiya

Mascarenhas gave an instance of linear programming problems to show that the long-step affine scaling algorithm can fail to converge to an optimal solution when the step-size is $\lambda=0.999$. In this short note, we give a simple and clear geometrical explanation for this phenomenon in terms of the Newton barrier flow induced by projecting the homogeneous affine scaling vector field conically onto a hyperplane where the objective function is constant. Based on this interpretation, we show that the algorithm can fail for a step-size $\lambda \leq 0.91071$ which is shorter than $\lambda = 0.95$ and $0.99$ recommended for efficient implementations.

Research Memorandum No.596, The Institute of Statistical Mathematics, Tokyo, Japan, March, 1996.

Contact: T.Terlaky@dutiwv.twi.tudelft.nl