Structured matrices in unconstrained minimization methods

Structured matrix algebras L and a generalized BFGS-type iterative scheme have been recently exploited to introduce low complexity quasi-Newton methods, named LQN, for solving general (nonstructured)minimization problems. In this paper we study the "inverse" LQN methods, which define inverse Hessian approximations by an inverse BFGS-type updating procedure. As the known LQN, the inverse LQN methods can be implemented with only O(n log_2 n) arithmetic operations per step and O(n) memory allocations. Moreover, they turn out to be particularly useful in the study of conditions on L which guarantee the extension of the fast BFGS local convergence properties to LQN-type algorithms