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

摘要

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.