##
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