Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior-Point Methods
Renato D. C. Monteiro, Jerome W. O’Neal, Takashi Tsuchiya · SIAM Journal on Optimization · 2004
Solving systems of linear equations with "normal" matrices of the form AD 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.