Optimization Online


Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

Renato D.C. Monteiro (monteiro***at***isye.gatech.edu)
Jerome O'Neal (joneal***at***isye.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/2003
Entry Accepted: 10/31/2003
Entry Last Modified: 11/03/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society