title: Convergence Analysis of a Long-Step Primal-Dual
Infeasible Interior-Point LP Algorithm
Based on Iterative Linear Solvers
abstract:
In this talk, we consider a
modified version of a well-known long-step primal-dual
infeasible IP algorithm for solving the linear program
$\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$,
where the search directions
are computed by means of an iterative linear solver
applied to a preconditioned normal system of equations.
We show that the number of (inner) iterations of
the iterative linear solver at each (outer) iteration
of the algorithm is bounded by a polynomial in $m$, $n$ and
a certain condition number associated with $A$, while
the number of outer iterations is bounded
by $\O(n^2 \log \epsilon^{-1} )$, where
$\epsilon$ is a given relative accuracy level. As a special case,
it follows that the total number of inner iterations is polynomial
in $m$ and $n$ for the minimum cost network flow problem.