  


Convergence Analysis of a LongStep PrimalDual Infeasible InteriorPoint LP Algorithm Based on Iterative Linear Solvers
Renato D.C. Monteiro (monteiroisye.gatech.edu) Abstract: In this paper, we consider a modified version of a wellknown longstep primaldual 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, interiorpoint 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/2003 Modify/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  