×

Uniform boundedness of a preconditioned normal matrix used in interior-point methods. (English) Zbl 1075.65085

Summary: Solving systems of linear equations with “normal” matrices of the form \(A D^2A^{T}\) is a key ingredient in the computation of search directions for interior-point algorithms. We establish 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.

MSC:

65K05 Numerical mathematical programming methods
65F35 Numerical computation of matrix norms, conditioning, scaling
90C05 Linear programming
90C35 Programming involving graphs or networks
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI