Applied Mathematics and Optimization, Vol.40, No.3, 287-314, 1999
A note on Mascarenhas' counterexample about global convergence of the affine scaling algorithm
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 with the step-size lambda = 0.999. In this 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 "any" lambda greater than about 0.91 (a more precise value is 0.91071), which is considerably shorter than lambda = 0.95 and 0.99 recommended for efficient implementations.