  


Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods
Renato D. C. Monteiro (monteiroisye.gatech.edu) 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 interiorpoint algorithms. In this article, we establish that a wellknown 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 nodearc 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(nm+1)$, where $m$ and $n$ are the number of nodes and arcs of the network. 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, March 2003. Download: [Postscript][PDF] Entry Submitted: 03/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  