On Updating the Inverse of a KKT Matrix

摘要

A KKT matrix, W say, is symmetric and nonsingular, with a leading n x n block that has a conditional positive definite property and a trailing m x m block that is identically zero, the dimensions of W being (n+m) x (n + m). The author requires the inverse matrix H = W~(-1) explicitly in an iterative algorithm for unconstrained minimization without derivatives, and only one of the first n rows and columns of W is altered on each iteration. The corresponding change to H can be calculated in O(n~2) operations. We study the accuracy and stability of some methods for this updating problem, finding that huge errors can occur in the application to optimization, which tend to be corrected on later iterations. Let Ω be the leading n x n submatrix of H. We give particular attention to the remark that the rank of Ω is only n — m, due to the zero block of W. Thus Ω can be expressed as the sum of n—m matrices of rank one, and this factorization can also be updated in O(n~2) operations. We find, in theory and in practice, that the use of the factored form of Ω reduces the damage from rounding errors and improves the stability of the updating procedure. These conclusions are illustrated by numerical results from the algorithm for unconstrained minimization.