No. 872

Title:

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

Author(s):

Renato D. C. Monteiro (School of Industrial and Systems Engineering, Georgia Institute of Technology);
Jerome W. O'Neal (School of Industrial and Systems Engineering, Georgia Institute of Technology);
Takashi, Tsuchiya (The Institute of Statistical Mathematics)

Key words:

Abstract:

Systems of linear equations with ``normal'' matrices of the form AD2AT is a key ingredient in the computation of search directionsfor 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 corrsponding 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.