Title: On the Quadratic Convergence of the Simplified Mizuno--Todd--Ye Algorithm for Linear Programming
Abstract: 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 analytic 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 analytic center). The simplified predictor-corrector algorithm requires only one linear solve per iteration in contrast to the two linear solves per iteration required by the original predictor-corrector algorithm.