A Quadratically Convergent O(square root of nL-Iteration Algorithm for Linear Programming

Abstract
Recently it was demonstrated that Mizuno-Todd-Ye's predictor-corrector interior-point algorithm for linear programming maintains the O(square root of nL)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish he quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.

This publication has 0 references indexed in Scilit: