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 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.
Entry Submitted: 03/31/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|