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