Global and Polynomial-Time Convergence of an Infeasible-Interior-Point Algorithm Using Inexact Computation

Shinji Mizuno and Florian Jarre

In this paper, we propose an infeasible-interior-point algorithm for solving a primal-dual linear programming problem. The algorithm uses inexact computations for solving a linear system of equations at each iteration. Under a very mild assumption on the inexactness we show that the algorithm finds an approximate solution of the linear program or detects infeasibility of the program. The assumption on the inexact computation is satisfied if the approximation to the solution of the linear system is just a little bit ``better'' than the trivial approximation 0. We also give a sufficient condition to achieve polynomial-time convergence of the algorithm.

Research Memorandum 605, The Institute of Statistical Mathematics, Tokyo, Japan