Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems |
| |
Authors: | T. Tsuchiya |
| |
Affiliation: | (1) Institute of Statistical Mathematics, Minami-Azabu, Minato-Ku, Tokyo, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Linear programming interior-point methods Iri-Imai algorithm local analysis degenerate problems |
本文献已被 SpringerLink 等数据库收录! |
|