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

Abstract
In this note we consider a large step modification of the Mizuno-Todd-Ye O(square root of nL) predictor-corrector interior-point algorithm for linear programming. We demonstrate that the modified algorithm maintains its O(square root of nL)-iteration complexity, while exhibiting superlinear convergence for general problems and quadratic convergence for nondegenerate problems. To our knowledge, this is the first construction of a superlinearly convergent algorithm with O(square root of nL)-iteration complexity.

This publication has 0 references indexed in Scilit: