Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

Renato D. C. Monteiro (monteiroisye.gatech.edu)
Jerome W. O'Neal (jonealisye.gatech.edu)
Takashi Tsuchiya (tsuchiyasun312.ism.ac.jp)

Abstract: Solving systems of linear equations with ``normal'' matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over the set of all positive diagonal matrices. In particular, we show that when $A$ is the node-arc incidence matrix of a connected directed graph with one of its rows deleted, then the condition number of the corresponding preconditioned normal matrix is bounded above by $m(n-m+1)$, where $m$ and $n$ are the number of nodes and arcs of the network.

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, March 2003.

Download: [Postscript][PDF]

Entry Submitted: 03/31/2003
Entry Accepted: 03/31/2003
Entry Last Modified: 12/03/2003

Modify/Update this entry