Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal–dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal–dual variant of the Iri–Imai method and uses modified Newton search directions to minimize the Tanabe–Todd–Ye potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal–dual interior-point algorithms that do not follow the central path.