Measures for Symmetric Rank-One Updates

1994/11/01 by Henry Wolkowicz

paper · doi:10.1287/moor.19.4.815

Abstract

Measures of deviation of a symmetric positive definite matrix from the identity are derived. They give rise to symmetric rank-one, SR1, type updates. The measures are motivated by considering the volume of the symmetric difference of the two ellipsoids, which arise from the current and updated quadratic models in quasi-Newton methods. The measure defined by the problem—maximize the determinant subject to a bound of 1 on the largest eigenvalue—yields the SR1 update. The measure σ(A) = λ 1 (A)/det(A) 1/ n yields the optimally conditioned, sized, symmetric rank-one updates. The volume considerations also suggest a ‘correction’ for the initial stepsize for these sized updates. It is then shown that the σ-optimal updates, as well as the Oren-Luenberger self-scaling updates, are all optimal updates for the κ measure, the l 2 condition number. Moreover, all four sized updates result in the same largest (and smallest) ‘scaled’ eigenvalue and corresponding eigenvector. In fact, the inversesized BFGS is the mean of the σ-optimal updates, while the inverse of the sized DFP is the mean of the inverses of the σ-optimal updates. The difference between these four updates is determined by the middle n − 2 scaled eigenvalues. The κ measure also provides a natural Broyden class replacement for the SR1 when it is not positive definite.

Related

• Approximation of sequences of symmetric matrices with the symmetric rank-one algorithm and applications
• Multiple-rank Modification of Symmetric Eigenvalue Problem
• Low rank approximation of positive semi-definite symmetric matrices using Gaussian elimination and volume sampling
• Symmetric rank-one updates from partial spectrum with an application to\n out-of-sample extension
• On the rank-one approximation of symmetric tensors