On the Quadratic Convergence of the Simplified Mizuno-Todd-Ye Algorithm for Linear Programming

It is known that the Mizuno-Todd-Ye predictor-corrector primal-dual Newton interior-point method generates a duality gap sequence which converges quadratically to zero, and this is accomplished with an iteration complexity of O (sqrt(n) L). Very recently the present authors demonstrated that the iteration sequence generated by this method converges, and this convergence is to the analytical center of the solution set. In the current work we show that within a finite number of iterations the Newton corrector step can be replaced with a simplified Newton corrector step and the resulting algorithm maintains O (sqrt(n) L) iteration complexity, quadratic convergence of the duality gap sequence to zero, and convergence of the iteration sequence, however not necessarily to the analytical center. The simplified predictor-corrector algorithm requires only one linear solve per iteration in contrast to two linear solves per iteration required by the original predictor-corrector algorithm