Matrix algebras in Quasi-Newton methods for unconstrained minimization

Summary.  In this paper a new class of quasi-Newton methods, named ℒQN, is introduced in order to solve unconstrained minimization problems. The novel approach, which generalizes classical BFGS methods, is based on a Hessian updating formula involving an algebra ℒ of matrices simultaneously diagonalized by a fast unitary transform. The complexity per step of ℒQN methods is O(n log n), thereby improving considerably BFGS computational efficiency. Moreover, since ℒQN's iterative scheme utilizes single-indexed arrays, only O(n) memory allocations are required. Global convergence properties are investigated. In particular a global convergence result is obtained under suitable assumptions on f. Numerical experiences [7] confirm that ℒQN methods are particularly recommended for large scale problems. Received December 30, 2001 / Revised version received December 20, 2001 / Published online November 27, 2002 Mathematics Subject Classification (1991): 65K10 Correspondence to: P. Zellini