A dimer-type saddle search algorithm with preconditioning and linesearch

Gould, N.; Ortner, C.; Packwood, D.

doi:10.1090/mcom/3096

A dimer-type saddle search algorithm with preconditioning and linesearch
HTML articles powered by AMS MathViewer

by N. Gould, C. Ortner and D. Packwood PDF

Math. Comp. 85 (2016), 2939-2966 Request permission

Abstract:

The dimer method is a Hessian-free algorithm for computing saddle points. We augment the method with a linesearch mechanism for automatic step size selection as well as preconditioning capabilities. We prove local linear convergence. A series of numerical tests demonstrate significant performance gains.

References

P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton University Press, Princeton, NJ, 2008. With a foreword by Paul Van Dooren. MR 2364186, DOI 10.1515/9781400830244
P.-A. Absil, Robert Mahony, and Jochen Trumpf, An extrinsic look at the Riemannian Hessian, Geometric science of information, Lecture Notes in Comput. Sci., vol. 8085, Springer, Heidelberg, 2013, pp. 361–368. MR 3126065, DOI 10.1007/978-3-642-40020-9_{3}9
A. Banerjee, N. Adams, J. Simons, and R. Shepard, Search for stationary points on surfaces, The Journal of Physical Chemistry 89 (1985), 52–57.
G.T. Barkema and N. Mousseau, Event-based relaxation of continuous disordered systems, Physical Review Letters 77 (1996), 4358.
G.T. Barkema and N. Mousseau, The activation-relation technique: an efficient algorithm for sampling energy landscapes, Computational Materials Science 20 (2001), nos. (3–4), 285–292.
E. Cances, F. Legoll, M.C. Marinica, K. Minoukadeh, and F. Willaime, Some improvements of the activation-relaxation technique method for finding transition pathways on potential energy surfaces, The Journal of Chemical Physics 130 (2009), 114711.
C.J. Cerjan and W.H. Miller, On finding transition states, Journal of Chemical Physics 75 (1981), 2800.
Nicholas I. M. Gould and Sven Leyffer, An introduction to algorithms for nonlinear optimization, Frontiers in numerical analysis (Durham, 2002) Universitext, Springer, Berlin, 2003, pp. 109–197. MR 2006967
N. I. M. Gould, C. Ortner, and D. Packwood, An efficient dimer method with preconditioning and linesearch. ArXiv:1407.2817v2.
G. Henkelman and H. Jónsson, A dimer method for finding saddle points on high dimensional potential surfaces using only first derivatives, Journal of Chemical Physics 111 (1999), no. 5, 7010–7022.
A. Heyden, A. T. Bell, and F. J. Keil, Efficient methods for finding transition states in chemical reactions: Comparison of improved dimer method and partitioned rational function optimization method, Journal of Chemical Physics 123 (2005), 224101.
H. Jónsson, G. Mills, and K. W. Jacobsen, Nudged elastic band for finding minimum energy paths of transitions, In G. Ciccotti B. J. Berne and D. F. Coker, editors, Classical and quantum dynamics in condensed phase simulations 385 World Scientific, 1998.
J. Kästner and P. Sherwood, Superlinearly converging dimer method for transition state search, The Journal of Chemical Physics 128 (2008), 014106.
Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 0042791, DOI 10.6028/jres.045.026
Dong C. Liu and Jorge Nocedal, On the limited memory BFGS method for large scale optimization, Math. Programming 45 (1989), no. 3, (Ser. B), 503–528. MR 1038245, DOI 10.1007/BF01589116
E. Machado-Charry, L.K. Beland, D. Caliste, Luigi Genovese, T. Deutsch, N. Mousseau, and P. Pochet, Optimized energy landscape exploration using the ab initio based activation-relaxation technique, Journal of Chemical Physics 135 (2011), 034102.
M.C. Marinica, F. Willaime, and N. Mousseau, Energy landscape of small clusters of self-interstitial dumbbells in iron, Physical Review B 83 (2011), 094119.
N. Mousseau, L.K. Beland, P. Brommer, J.F. Joly, F. El-Mellouhi, E. Machado-Charry, M.C. Marinica, and P. Pochet, The activation-relaxation technique: Art nouveau and kinetic art, Journal of Atomic, Molecular and Optical Physics 2012 (2012), 952278.
B. A. Murtagh and R. W. H. Sargent, Computational experience with quadratically convergent minimisation methods, Comput. J. 13 (1970), 185–194. MR 266403, DOI 10.1093/comjnl/13.2.185
Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114, DOI 10.1007/b98874
R. A. Olsen, G. J. Kroes, G. Henkelman, A. Arnaldsson, and H. Jonsson, Comparison of methods for finding saddle points without knowledge of the final states, Journal of Chemical Physics 121 (2004), 9776.
J. Simons, P. Joergensen, H. Taylor, and J. Ozment, Walking on potential energy surfaces, The Journal of Physical Chemistry 87 (1983), 2745–2753.
B. P. Uberuaga, F. Montalenti, T. C. Germann, and A. F. Voter, Accelerated molecular dynamics methods, In S. Yip, editor, Handbook of Materials Modelling, Part A- Methods, page 629. Springer, 2005.
A. E. Perekatov V. S. Mikhalevich, N. N. Redkovskii, Methods of minimization of functions on a sphere and their applications, Cybernetics and Systems Analysis 23 (1987), no. 6, 721–730.
A. F. Voter, Accelerated molecular dynamics of infrequent events, Physical Review Letters 78 (1997), 3908.
A. F. Voter, Introduction to the kinetic Monte Carlo method, In K. E. Sickafus, E. A. Kotomin, and B. P. Uberuaga, editors, Radiation Effects in Solids, volume 235 of NATO Science Series, pages 1–23. Springer Netherlands, 2007.
E. Weinan, W. Ren, and E. Vanden-Eijnden, String method for the study of rare events, Physical Review B 66 (2002), 052301.
E. Weinan, W. Ren, and E. Vanden-Eijnden, Simplified and improved string method for computing the minimum energy path in barrier-crossing events, Journal of Chemical Physics 126 (2007), 164103.
Jingyan Zhang and Qiang Du, Shrinking dimer dynamics and its applications to saddle point search, SIAM J. Numer. Anal. 50 (2012), no. 4, 1899–1921. MR 3022203, DOI 10.1137/110843149
Lei Zhang, Jingyan Zhang, and Qiang Du, Finding critical nuclei in phase transformations by shrinking dimer dynamics and its variants, Commun. Comput. Phys. 16 (2014), no. 3, 781–798. MR 3233747, DOI 10.4208/cicp.250913.240314a