On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms

This paper presents a convergence rate analysis for interior point primal-dual linear programming algorithms. Conditions that guarantee Q-superlinear convergence are identified in two distinct theories. Both state that, under appropriate assumptions, Q-superlinear convergence is achieved by asymptotically taking the step to the boundary of the positive orthant and letting the barrier parameter approach zero at a rate that is superlinearly faster than the convergence of the duality gap to zero. The first theory makes no nondegeneracy assumption and explains why in recent numerical experimentation Q-superlinear convergence was always observed. The second theory requires the restrictive assumption of primal nondegeneracy. However, it gives the surprising result that Q-superlinear convergence can still be attained even if centering is not phased out, provided the iterates asymptotically approach the central path. The latter theory is extended to produce a satisfactory Q-quadratic convergence theory. It requires that the step approach the boundary as fast as the duality gap approaches zero and the barrier parameter approach zero as fast as the square of the duality gap approaches zero.