Davidon-Fletcher-Powell method

EX242 2.4.2 Rosenbrock problem by Davidon-Fletcher-Powell method M36... 

It is widely believed that, generally speaking, methods such as the Davidon-Fletcher-Powell method are superior to the Fletcher-Reeves method and, indeed, Fletcher suggests (see p. 82 of ref. 8) that typically the Fletcher-Reeves method will take about twice as many iterations as the Davidon-Fletcher-Powell method. 

This rank two correction has no numerical problems with small denominators, and it can be shown that is always positive definite if H is. This guarantees that d will always be a descent direction, thus overcoming one of the serious difficulties of the pure Newton method. The Davidon-Fletcher-Powell method works quite well, but it turns out that the slight modification below gives experimentally better results, even though it is theoretically equivalent. 

I is the identity matrix. The six first derivatives of the energy with respect to the strain components e, measure the forces acting on the unit cell. When combined with the atomic coordinates we get a matrix with 3N - - 6 dimensions. At a minimum not only should there be no force on any of the atoms but the forces on the unit cell should also be zero. Application of a standard iterative minimisation procedure such as the Davidon-Fletcher-Powell method will optimise all these degrees of freedom to give a strain-free final structure. In such procedures a reasonably accurate estimate of the initial inverse Hessian matrix is usually required to ensure that the changes in the atomic positions and in the cell dimensions are matched. 

The program uses several minimizing routines that can easily be chosen, such as the pit-mapping method developed by Sillen, but also Simplex, Davidon-Fletcher-Powell, and Monte Carlo methods of MINUIT package [53]. As for AR, up to third-degree equations can be used ... 

Various update methods carry the names of Broyden, Davidon, Fletcher, Goldfarb, Powell, and Shanno, in different combinations. We recommend a comprehensive textbook, namely... 

FR and PR refer to the Fletcher-Reeves and Polark-Ribi6re nonlinear CG versions. DFP is a rank-1 QN method, credited to Davidon, Fletcher, and Powell. 

The methods differ in the formula used to generate the sequence S, k=0,l,2,., and after Fletcher and Powell s 3 analysis of Davidon s method a whole spate of formulae were invented in the sixties. Broyden 4 introduced some rationalization by identifying a one-parameter family, and recommended a particular member, now commonly referred to as the BFGS (Broyden-Fletcher-Goldfarb-Shanno) formula. Huang 5 widened the family, but by the end of the sixties numerical experience was producing a consensus that the BFGS formula was the most robust of the formulae available. The formula is... 

The first generally successful method was presented by Davidon (1959), who called it a variable metric method. It was subsequently developed by Fletcher and Powell (1963). They show, and it is straightforward to verify directly, that the following rank two correction satisfies the basic recursion requirement. 

The first methods belonging to the quasi-Newton family, specifically the methods proposed by Davidon (1959), and Fletcher and Powell (1963), calculate Hj, which is an approximation of the inverse of G . The inverse matrix was used since, by knowing it, it was no longer necessary to solve the hnear system (3.137), but simply execute the product ... 

---