On quadratic convergence of the O(root nL)-iteration homogeneous and self-dual linear programming algorithm

In this paper, we show that Ye-Todd-Mizuno's O(root nL)-iteration homogeneo us and self-dual linear programming (LP) algorithm possesses quadratic conv ergence of the duality gap to zero. In the case of infeasibility, this show s that a homogenizing variable quadratically converges to zero (which prove s that at least one of the primal and dual LP problems is infeasible) and i mplies that the iterates of the (original) LP variable quadratically diverg e. Thus, we have established a complete asymptotic convergence result for i nterior-point algorithms without any assumption on the LP problem.