We study the limiting properties of the affine-scaling directions for linear programming problems. The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms. We establish new relations between this measure and some other complexity measures which are used in the complexity analyses of algorithms for linear programming. We also provide a new characterization of the smallest large variable complexity measure of Ye.
Citation
Research Report 2003--24, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, August 2003