On the limiting properties of the affine-scaling directions

Abstract

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.