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

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.

Citation

Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, March 2003.

Article

Download

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