Advanced Search
Article Contents
Article Contents

Global optimization-based dimer method for finding saddle points

  • * Corresponding author: Lei Zhang

    * Corresponding author: Lei Zhang
Abstract Full Text(HTML) Figure(4) / Table(3) Related Papers Cited by
  • Searching saddle points on the potential energy surface is a challenging problem in the rare event. When there exist multiple saddle points, sampling different initial guesses are needed in local search methods in order to find distinct saddle points. In this paper, we present a novel global optimization-based dimer method (GOD) to efficiently search saddle points by coupling ant colony optimization (ACO) algorithm with optimization-based shrinking dimer (OSD) method. In particular, we apply OSD method as a local search algorithm for saddle points and construct a pheromone function in ACO to update the global population. By applying a two-dimensional example and a benchmark problem of seven-atom island on the (111) surface of an FCC crystal, we demonstrate that GOD shows a significant improvement in computational efficiency compared with OSD method. Our algorithm is the first try to apply the global optimization technique in searching saddle points and it offers a new framework to open up possibilities of adopting other global optimization methods.

    Mathematics Subject Classification: 37M05, 49K35, 37N30, 34K28, 65P99.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An example of $ B_2 $ function that has one minimum M0, four maxima M1-M4, and four index-1 saddle points S1-S4. (A): modified $ \kappa $ in Eq. (15). (B): pheromone function in Eq. (16). The black lines are the contours of the $ B_2 $ function. The parameters used in Eq. (16) are $ \alpha = 0.75,a = 0.05,b = 100 $

    Figure 2.  2D example with three different initial samplings: (A) circle sampling; (B) uniform sampling; (C) random sampling. White dots represent the initial points, green dots are the points deleted in the halfway, and red dots are the saddle points. The yellow lines represent the dynamic paths by GOD

    Figure 3.  Two initial samplings for the seven-atom island: (A) sample 1: shift the parallel $ (2,7) $ and $ (4,5) $ atoms simultaneously to get $ 100 $ initial points; (B) sample 2: shift parallel atoms along six directions to get $ 300 $ initial points

    Figure 4.  Seven-atom island example with two different initial samplings: (A) sample 1 with 100 initial points; (B) sample 2 with 300 initial points. Blue line represents the number of moving points, yellow line represents the number of deleted points, and red line corresponds to the number of saddle points. Some parameters are $ \delta_1 = 1.0, a = b = 10, \alpha = 0.5 $. $ step_{ls} = 20 $ for sample 1 and $ step_{ls} = 30 $ for sample 2

    Table 1.  Comparison of OSD method and GOD method in the 2D example

    sample method initial points force evaluations saddles
    circle OSD 50 7270 4
    circle GOD 50 1249 4
    uniform OSD 400 44212 22
    uniform GOD 400 8716 22
    random OSD 400 45581 22
    random GOD 400 8352 22
     | Show Table
    DownLoad: CSV

    Table 2.  Comparison of OSD method and GOD method in the seven-atom island problem

    sample method cputime(s) force evaluations saddles
    sample 1 OSD 325.781 80946 29
    sample 1 GOD 188.375 45072 29
    sample 2 OSD 1022.720 250941 92
    sample 2 GOD 618.906 140624 92
     | Show Table
    DownLoad: CSV

    Table 3.  Parameter sensitivity of GOD method for Sample 1 in the seven-atom island problem

    parameters cputime(s) force evaluations saddles
    $ \delta_1 $ 1.0 188.375 45072 29
    0.75 226.781 49225 29
    0.5 234.141 51353 29
    $ \alpha $ 0.25 226.547 49972 29
    0.5 226.781 49225 29
    0.75 226.875 49929 29
    $ a $ 1 223.688 49036 29
    10 226.781 49225 29
    100 224.531 48894 29
    1000 234.359 51131 29
    $ b $ 1 223.688 49036 29
    10 226.781 49225 29
    100 204.297 48282 29
    1000 191.656 45857 29
     | Show Table
    DownLoad: CSV
  • [1] O. Andrzej and K. Stanislaw, Evolutionary algorithms for global optimization, Global Optimization, (2006), 267–300. doi: 10.1007/0-387-30927-6_12.
    [2] J. Baker, An algorithm for the location of transition states, Journal of Computational Chemistry, 7 (1986), 385-395.  doi: 10.1002/jcc.540070402.
    [3] M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1 (1997), 53-66.  doi: 10.1109/4235.585892.
    [4] J. Duncan, Q. L. Wu, K. Promislow and G. Henkelman, Biased gradient squared descent saddle point finding method, The Journal of Chemical Physics, 140 (2014), 194102. doi: 10.1063/1.4875477.
    [5] C. A. Floudas, Deterministic Global Optimization: Theory, Methods and Applications, Nonconvex Optimization and its Applications, 37. Kluwer Academic Publishers, Dordrecht, 2000. doi: 10.1007/978-1-4757-4949-6.
    [6] W. G. GaoJ. Leng and X. Zhou, Iterative minimization algorithm for efficient calculations of transition states, Journal of Computational Physics, 309 (2016), 69-87.  doi: 10.1016/j.jcp.2015.12.056.
    [7] W. L. GoffeG. D. Ferrier and J. Rogers, Global optimization of statistical functions with simulated annealing, Journal of Econometrics, 60 (1994), 65-99.  doi: 10.1016/0304-4076(94)90038-8.
    [8] S. T. Gu and X. Zhou, Convex splitting method for the calculation of transition states of energy functional, Journal of Computational Physics, 353 (2018), 417-434.  doi: 10.1016/j.jcp.2017.10.028.
    [9] Y. C. HanY. C. HuP. W. Zhang and L. Zhang, Transition pathways between defect patterns in confined nematic liquid crystals, Journal of Computational Physics, 396 (2019), 1-11.  doi: 10.1016/j.jcp.2019.06.028.
    [10] Y. C. HanZ. R. XuA.-C. Shi and L. Zhang, Pathways connecting two opposed bilayers with a fusion pore: A molecularly-informed phase field approach, Soft Matter, 16 (2020), 366-374.  doi: 10.1039/C9SM01983A.
    [11] G. Henkelman and H. Jonsson, A dimer method for finding saddle points on high dimensional potential surfaces using only first derivatives, Journal of Chemical Physics, 111 (1999), 7010. doi: 10.1063/1.480097.
    [12] 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, The Journal of Chemical Physics, 123 (2005), 224101. doi: 10.1063/1.2104507.
    [13] J. Kästner and P. Sherwood, Superlinearly converging dimer method for transition state search, The Journal of Chemical Physics, 128 (2008), 014106. doi: 10.1063/1.2815812.
    [14] Z. Q. Li and H. A. Scheraga, Monte carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Nat. Acad. Sci. U.S.A., 84 (1987), 6611-6615.  doi: 10.1073/pnas.84.19.6611.
    [15] T. LiaoK. SochaM. A. M. de OcaT. Stützle and M. Dorigo, Ant colony optimization for mixed-variable optimization problems, IEEE Transactions on Evolutionary Computation, 18 (2014), 503-518.  doi: 10.1109/TEVC.2013.2281531.
    [16] A. Lipowski and D. Lipowska, Roulette-wheel selection via stochastic acceptance, Physica A: Statistical Mechanics and Its Applications, 391 (2012), 2193-2196.  doi: 10.1016/j.physa.2011.12.004.
    [17] E. Machado-Charry, L. K. Béland, D. Caliste, L. Genovese, T. Deutsch, N. Mousseau and P. Pochet, Optimized energy landscape exploration using the ab initio based activation-relaxation technique, The Journal of Chemical Physics, 135 (2011), 034102. doi: 10.1063/1.3609924.
    [18] J. MilnorMorse Theory, Annals of Mathematics Studies, No. 51 Princeton University Press, Princeton, N.J., 1963.  doi: 10.1515/9781400881802.
    [19] N. Mousseau and G. Barkema, Traveling through potential energy landscapes of disordered materials: The activation-relaxation technique, Physical Review E, 57 (1998), 2419. doi: 10.1103/PhysRevE.57.2419.
    [20] R. Olsen, G. Kroes, G. Henkelman, A. Arnaldsson and H. Jónsson, Comparison of methods for finding saddle points without knowledge of the final states, The Journal of Chemical Physics, 121 (2004), 9776. doi: 10.1063/1.1809574.
    [21] M. Plasencia GutiérrezC. Argáez and H. Jónsson, Improved minimum mode following method for finding first order saddle points, Journal of Chemical Theory and Computation, 13 (2017), 125-134.  doi: 10.1021/acs.jctc.5b01216.
    [22] A. Poddey and P. E. Blochl, Dynamical dimer method for the determination of transition states with ab initio molecular dynamics, The Journal of Chemical Physics, 128 (2008), 044107. doi: 10.1063/1.2826338.
    [23] R. PoliJ. Kennedy and T. Blackwell, Particle swarm optimization, Swarm Intelligence, 1 (2007), 33-57.  doi: 10.1007/s11721-007-0002-0.
    [24] Z. D. Pozun, K. Hansen, D. Sheppard, M. Rupp, K.-R. Müller and G. Henkelman, Optimizing transition states via kernel-based machine learning, The Journal of Chemical Physics, 136 (2012), 174101. doi: 10.1063/1.4707167.
    [25] S. U. SeçkinerY. EroǧluM. Emrullah and T. Dereli, Ant colony optimization for continuous functions by using novel pheromone updating, Applied Mathematics and Computation, 219 (2013), 4163-4175.  doi: 10.1016/j.amc.2012.10.097.
    [26] D. Sheppard, R. Terrell and G. Henkelman, Optimization methods for finding minimum energy paths, The Journal of Chemical Physics, 128 (2008), 134106. doi: 10.1063/1.2841941.
    [27] K. Socha and M. Dorigo, Ant colony optimization for continuous domains, European Journal of Operational Research, 185 (2008), 1155-1173.  doi: 10.1016/j.ejor.2006.06.046.
    [28] W. N. E and X. Zhou, The gentlest ascent dynamics, Nonlinearity, 24 (2011), 1831-1842.  doi: 10.1088/0951-7715/24/6/008.
    [29] W. Wenzel and K. Hamacher, Stochastic tunneling approach for global minimization of complex potential energy landscapes, Physical Review Letters, 82 (1999), 3003-3007.  doi: 10.1103/PhysRevLett.82.3003.
    [30] P. Xiao, Q. Wu and G. Henkelman, Basin constrained $\kappa$-dimer method for saddle point finding, Journal of Chemical Physics, 141 (2014), 164111. doi: 10.1063/1.4898664.
    [31] J. Y. Yin, L. Zhang and P. W. Zhang, High-index optimization-based shrinking dimer method for finding high-index saddle points, SIAM Journal on Scientific Computing, 41 (2019), A3576–A3595. doi: 10.1137/19M1253356.
    [32] J. Y. Zhang and Q. Du, Constrained shrinking dimer dynamics for saddle point search with constraints, Journal of Computational Physics, 231 (2012), 4745-4758.  doi: 10.1016/j.jcp.2012.03.006.
    [33] J. Y. Zhang and Q. Du, Shrinking dimer dynamics and its applications to saddle point search, SIAM Journal on Numerical Analysis, 50 (2012), 1899-1921.  doi: 10.1137/110843149.
    [34] L. Zhang, L.-Q. Chen and Q. Du, Morphology of critical nuclei in solid-state phase transformations, Physical Review Letters, 98 (2007), 265703. doi: 10.1103/PhysRevLett.98.265703.
    [35] L. ZhangL.-Q. Chen and Q. Du, Diffuse-interface approach to predicting morphologies of critical nucleus and equilibrium structure for cubic to tetragonal transformations, Journal of Computational Physics, 229 (2010), 6574-6584.  doi: 10.1016/j.jcp.2010.05.013.
    [36] L. Zhang, Q. Du and Z. Z. Zheng, Optimization-based shrinking dimer method for finding transition states, SIAM Journal on Scientific Computing, 38 (2016), A528–A544. doi: 10.1137/140972676.
    [37] L. Zhang, W. Q. Ren, A. Samanta and Q. Du, Recent developments in computational modelling of nucleation in phase transformations, Npj Computational Materials, 2 (2016), 16003. doi: 10.1038/npjcompumats.2016.3.
  • 加载中




Article Metrics

HTML views(486) PDF downloads(489) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint