No label defined (Q4338460)

This paper describes a new iterative algorithm for the minimization of a smooth function \(f(x)\), where \(x\in \mathbb{R}^n\), using only first-derivative information. There are two main classes of methods for this problem, namely conjugate gradient (CG) and quasi-Newton (QN) methods. It is recognized that successful QN algorithms such as BFGS have in general much better convergence properties than unpreconditioned CG algorithms, but the QN methods have one serious disadvantage: they require the storage of an \(n\times n\) matrix which is updated to resemble the Hessian of \(f\) -- or its inverse -- as the iteration proceeds. When the dimension \(n\) is large, the storage of such a matrix is impractical. Researchers have therefore produced variants of the standard QN algorithms in which a reduced amount of storage, of order \(n\) rather than \(n^2\), is used. This is achieved by storing the initial matrix in compact form, together with a prescribed number of individual updates. When this storage is filled, existing reduced storage algorithms are based on the idea of overwriting the new update information on one of the existing ones, while retaining the others unchanged. In this paper a new approach is proposed; in this, all updates are removed when the available storage is filled, but replaced by an `artificial' update, constructed so that the new QN matrix will mimic the behaviour of the previous one. The iteration can then resume in the normal QN fashion, until the space is again full and a further condensation of the accumulated update information is needed. It is shown that by this `update condensation' technique it is possible to develop a reduced storage QN algorithm which, for a wide class of `nearly quadratic' functions, will perform as well as the corresponding full QN method; this property is independent of the number of updates additional to the artificial one that are stored. The update condensation algorithms follow the QN approach in which it is the inverse of the Hessian matrix which is approximated.