Solving Limited-Memory BFGS Systems with Generalized Diagonal Updates.

In this paper, we investigate a formula to solve systems of the form (Bk + D)x = y, where Bk comes from a limited-memory BFGS quasi-Newton method and D is a diagonal matrix with diagonal entries di,i ≥ σ for some σ > 0. These types of systems arise naturally in large-scale optimization. We show that provided a simple condition holds on B0 and σ, the system (Bk + D)x = y can be solved via a recursion formula that requies only vector inner products. This formula has complexity M²n, where M is the number of L-BFGS updates and n ⪢ M is the dimension of x. We do not assume anything about the distribution of the values of the diagonal elements in D, and our approach is particularly for robust non-clustered values, which proves problematic for the conjugate gradient method. [ABSTRACT FROM AUTHOR]

Copyright of Proceedings of the World Congress on Engineering 2012 Volume I is the property of Newswood Limited and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)