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: [email protected]
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)