A lower bound on the number of iterations of long-step primal-dual linear programming algorithms

Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at least n¹’/³ iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, the authors further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neighborhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to that is implemented in practice.