Matrix algebras in Quasi-Newton methods for unconstrained minimization

In this paper a new class of quasi-Newton methods, named LQN, 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 L of matrices simultaneously diagonalized by a fast unitary transform. The complexity per step of LQN methods is O(n log_2 n), thereby improving considerably BFGS computational efficiency. Moreover, since LQN'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 LQN methods are particularly recommended for large scale problems.