Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation

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 whenever the primal–dual linear programming problem is feasible. 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.