A variation of Broyden class methods using Householder adaptive transforms
- PDF / 2,471,859 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 186 Views
A variation of Broyden class methods using Householder adaptive transforms S. Cipolla1 · C. Di Fiore2 · P. Zellini2 Received: 17 August 2017 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this work we introduce and study novel Quasi Newton minimization methods based on a Hessian approximation Broyden Class-type updating scheme, where a suitable matrix B̃ k is updated instead of the current Hessian approximation Bk . We identify conditions which imply the convergence of the algorithm and, if exact line search is chosen, its quadratic termination. By a remarkable connection between the projection operation and Krylov spaces, such conditions can be ensured using low complexity matrices B̃ k obtained projecting Bk onto algebras of matrices diagonalized by products of two or three Householder matrices adaptively chosen step by step. Experimental tests show that the introduction of the adaptive criterion, which theoretically guarantees the convergence, considerably improves the robustness of the minimization schemes when compared with a non-adaptive choice; moreover, they show that the proposed methods could be particularly suitable to solve large scale problems where L-BFGS is not able to deliver satisfactory performance. Keywords Unconstrained minimization · Quasi-Newton methods · Matrix algebras · Matrix projections preserving directions Mathematics Subject Classification 65K10 · 90C53 · 47J25 · 15B · 65F
* S. Cipolla [email protected] C. Di Fiore [email protected] P. Zellini [email protected] 1
University of Padua, Via Trieste 63, 35121 Padua, Italy
2
University of Rome “Tor Vergata”, Via Della Ricerca Scientifica 1, 00133 Rome, Italy
13
Vol.:(0123456789)
S. Cipolla et al.
1 Introduction In minimizing a function f ∶ ℝn → ℝ , in order to reduce the computational cost per iteration and the memory required for implementation of the well known BFGS minimization method, it is proposed in [15–19] to use a BFGS-type updating scheme which updates, at each step, a suitable approximation of the Hessian approximation Bk , usually denoted by B̃ k . This scheme is named L QN when the matrix B̃ k is the projection LBk of the matrix Bk in a matrix algebra L of matrices simultaneously diagonalized by a given unitary transform U (we write L ∶= sd U , see (2) for a precise definition). The implementation of the L QN turns out to be very cheap when U defines a low complexity transform. While in [4, 9, 23] L is a fixed matrix algebra, in [15, 17] it is observed that an adaptive choice of L , i.e, using different algebras L(k) for each iteration k, could preserve more information from the original matrix Bk , and thus improve the efficiency of LQN. In [12] it is introduced a convergent L(k) QN scheme whose effectiveness is shown by preliminary numerical experiences. The main contribution of this work is twofold. On the one hand we extend the theoretical framework and the convergence theory developed in [12, 16] for BFGStype techniques to the restricted Broyden Cl
Data Loading...
