Optimization Online


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

Renato D. C. Monteiro (monteiro***at***isye.gatech.edu)
Jerome W. O'Neal (joneal***at***isye.gatech.edu)
Takashi Tsuchiya (tsuchiya***at***sun312.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

  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