A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming

The choice of the centering (or barrier) parameter and the step length parameter are the fundamental issues in primal-dual interior-point algorithms for linear programming. Various choices for these two parameters have been proposed that lead to polynomial algorithms. Recently, Zhang, Tapia and Dennis gave conditions that these choices must satisfy in order to achieve quadratic or superlinear convergence. However, it has not been shown that these conditions for fast convergence are compatible with the choices that lead to polynomiality. It is worth noting that none of the existing polynomial algorithms satisfies these fast convergence requirements. This paper gives an affirmative answer to the question: can an algorithm be both polynomial and superlinearly convergent? We construct and analyze a "large step" algorithm that possesses both polynomiality and Q-superlinear convergence. For nondegenerate problems, the convergence rate is actually Q-quadratic