Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


A dimer-type saddle search algorithm with preconditioning and linesearch

Authors: N. Gould, C. Ortner and D. Packwood
Journal: Math. Comp. 85 (2016), 2939-2966
MSC (2010): Primary 65K99, 90C06, 65Z05
Published electronically: March 22, 2016
MathSciNet review: 3522976
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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
  • [2] 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,
  • [3] A. Banerjee, N. Adams, J. Simons, and R. Shepard,
    Search for stationary points on surfaces,
    The Journal of Physical Chemistry 89 (1985), 52-57.
  • [4] G.T. Barkema and N. Mousseau,
    Event-based relaxation of continuous disordered systems,
    Physical Review Letters 77 (1996), 4358.
  • [5] 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.
  • [6] 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.
  • [7] C.J. Cerjan and W.H. Miller,
    On finding transition states,
    Journal of Chemical Physics 75 (1981), 2800.
  • [8] 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
  • [9] N. I. M. Gould, C. Ortner, and D. Packwood,
    An efficient dimer method with preconditioning and linesearch.
  • [10] 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.
  • [11] 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.
  • [12] 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.
  • [13] J. Kästner and P. Sherwood,
    Superlinearly converging dimer method for transition state search,
    The Journal of Chemical Physics 128 (2008), 014106.
  • [14] 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
  • [15] 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,
  • [16] 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.
  • [17] 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.
  • [18] 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.
  • [19] B. A. Murtagh and R. W. H. Sargent, Computational experience with quadratically convergent minimisation methods, Comput. J. 13 (1970), 185–194. MR 0266403,
  • [20] Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114
  • [21] 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.
  • [22] J. Simons, P. Joergensen, H. Taylor, and J. Ozment,
    Walking on potential energy surfaces,
    The Journal of Physical Chemistry 87 (1983), 2745-2753.
  • [23] 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.
  • [24] 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.
  • [25] A. F. Voter,
    Accelerated molecular dynamics of infrequent events,
    Physical Review Letters 78 (1997), 3908.
  • [26] 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.
  • [27] E. Weinan, W. Ren, and E. Vanden-Eijnden,
    String method for the study of rare events,
    Physical Review B 66 (2002), 052301.
  • [28] 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.
  • [29] 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,
  • [30] 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,

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65K99, 90C06, 65Z05

Retrieve articles in all journals with MSC (2010): 65K99, 90C06, 65Z05

Additional Information

N. Gould
Affiliation: Scientific Computing Department, STFC-Rutherford Appleton Laboratory, Chilton, OX11 0QX, United Kingdom

C. Ortner
Affiliation: Mathematics Institute, Zeeman Building, University of Warwick, Coventry CV4 7AL, United Kingdom

D. Packwood
Affiliation: Mathematics Institute, Zeeman Building, University of Warwick, Coventry CV4 7AL, United Kingdom

Keywords: Saddle search, perconditioning, convergence, dimer method
Received by editor(s): July 30, 2014
Received by editor(s) in revised form: April 28, 2015
Published electronically: March 22, 2016
Additional Notes: This work was supported in part by EPSRC grants EP/J021377/1 and EP/J022055/1.
Article copyright: © Copyright 2016 American Mathematical Society