Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems

A local analysis of the Iri-Imai algorithm for linear programming is given to demonstrate quadratic convergence under degeneracy. Specifically, we show that the algorithm with an exact line search either terminates after a finite number of iterations yielding a point on the set of optimal solutions or converges quadratically to one of the relative analytic centers of the faces of the set of optimal solutions including vertices. Mostly, the sequence generated falls into one of the optimal vertices, and it is rare that the sequence converges to the relative analytic center of a face whose dimension is greater than or equal to one.This paper is based on Ref. 1.The author thanks Professor Kunio Tanabe of the Institute of Statistical Mathematics for valuable comments as well as stimulating discussions.