- Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers Renato D.C. Monteiro (monteiroisye.gatech.edu) Jerome O'Neal (jonealisye.gatech.edu) Abstract: In this paper, 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. Keywords: Linear programming, interior-point methods, polynomial bound, network flow problems, condition number, preconditioning, iterative methods for linear equations, normal matrix. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Network Optimization Citation: Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, October 2003. Download: [Postscript][PDF]Entry Submitted: 10/31/2003Entry Accepted: 10/31/2003Entry Last Modified: 11/03/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.