Improvement of the Nelder-Mead method using Direct Inversion in Iterative Subspace
Tóm tắt
The Nelder-Mead (NM) method is a popular derivative-free optimization algorithm owing to its fast convergence and robustness. However, it is known that the method often fails to converge or costs a long time for a large-scale optimization. In the present study, the NM method has been improved using direct inversion in iterative subspace (DIIS). DIIS is a technique to accelerate an optimization method, extrapolating a better intermediate solution from linear-combination of the known ones. We compared runtimes of the new method (NM-DIIS) and the conventional NM method using unimodal test functions with various dimensions. The NM-DIIS method showed better results than the original NM on average when the dimension of the objective function is high. Long tails of the runtime distributions in the NM method have disappeared when DIIS was applied. DIIS has also been implemented in the quasi-gradient method, which is an improved version of the NM method developed by Pham et al. [IEEE Trans. Ind. Informatics, 7 (2011) 592]. The combined method also performed well especially in an upwardly convex test function. The present study proposes a practical optimization strategy and proves the versatility of DIIS.
Tài liệu tham khảo
Ali AF, Tawhid MA (2016) A hybrid cuckoo search algorithm with Nelder Mead method for solving global optimization problems. Springerplus 5:473. https://doi.org/10.1186/s40064-016-2064-1
Alvarez-Vázquez LJ, Júdice JJ, Martínez A et al (2013) On the optimal design of river fishways. Optim Eng 14:193–211. https://doi.org/10.1007/s11081-011-9175-x
Amano K, Hayashi T, Hashimoto K et al (2018) Potential of mean force between spherical particles in an ionic liquid and its decomposition into energetic and entropic components: an analysis using an integral equation theory. J Mol Liq 257:121–131. https://doi.org/10.1016/j.molliq.2018.02.089
Amano K, Sawazumi R, Imamura H et al (2020) An improved model-potential-free analysis of the structure factor obtained from a small-angle scattering: acquisitions of the pair distribution function and the pair potential. Chem Lett 49:1017–1021. https://doi.org/10.1246/cl.200292
Amano K, Yokota Y, Ichii T et al (2017) A relationship between the force curve measured by atomic force microscopy in an ionic liquid and its density distribution on a substrate. Phys Chem Chem Phys 19:30504–30512. https://doi.org/10.1039/c7cp06948k
Donoso-Bravo A, Mailier J, Ruiz-Filippi G, Vande Wouwer A (2013) Identification in an anaerobic batch system: global sensitivity analysis, multi-start strategy and optimization criterion selection. Bioprocess Biosyst Eng 36:35–43. https://doi.org/10.1007/s00449-012-0758-5
Gao F, Han L (2012) Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Comput Optim Appl 51:259–277. https://doi.org/10.1007/s10589-010-9329-3
Han L, Neumann M (2006) Effect of dimensionality on the Nelder-Mead simplex method. Optim Methods Softw 21:1–16. https://doi.org/10.1080/10556780512331318290
Holland JH (1975) Adaptation in natural and artificial systems. MIT Press, Cambridge
Huang M, Aine CJ, Supek S et al (1998) Multi-start downhill simplex method for spatio-temporal source localization in magnetoencephalography. Electroencephalogr Clin Neurophysiol - Evoked Potentials 108:32–44. https://doi.org/10.1016/S0168-5597(97)00091-9
Irwin J, Reutzel EW, Michaleris P et al (2016) Predicting microstructure from thermal history during additive manufacturing for Ti-6Al-4V. J Manuf Sci Eng 138:1–11. https://doi.org/10.1115/1.4033525
Kelley CT (1999) Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition. SIAM J Optim 10:43–55. https://doi.org/10.1137/S1052623497315203
Kennedy J, Eberhart RC (1997) Discrete binary version of the particle swarm algorithm. Proc IEEE Int Conf Syst Man Cybern 5:4104–4108. https://doi.org/10.1109/icsmc.1997.637339
Kovalenko A, Ten-No S, Hirata F (1999) Solution of three-dimensional reference interaction site model and hypernetted chain equations for simple point charge water by modified method of direct inversion in iterative subspace. J Comput Chem 20:928–936. https://doi.org/10.1002/(SICI)1096-987X(19990715)20:9%3c928::AID-JCC4%3e3.0.CO;2-X
Lagarias JC, Poonen B, Wright MH (2012) Convergence of the restricted Nelder-Mead algorithm in two dimensions. SIAM J Optim 22:501–532. https://doi.org/10.1137/110830150
Luersen MA, Le Riche R (2004) Globalized Nelder-Mead method for engineering optimization. Comput Struct 82:2251–2260. https://doi.org/10.1016/j.compstruc.2004.03.072
Mesbahi T, Khenfri F, Rizoug N et al (2016) Dynamical modeling of Li-ion batteries for electric vehicle applications based on hybrid Particle Swarm–Nelder–Mead (PSO–NM) optimization algorithm. Electr Power Syst Res 131:195–204. https://doi.org/10.1016/j.epsr.2015.10.018
Nelder JA, Mead R (1965) A simplex method for function minimization. Comput J 7:308–313. https://doi.org/10.1093/comjnl/7.4.308
Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer, New York
Pham N, Malinowski A, Bartczak T (2011) Comparative study of derivative free optimization algorithms. IEEE Trans Ind Inform 7:592–600. https://doi.org/10.1109/TII.2011.2166799
Picard E (1893) Sur l’application des méthodes d’approximations successives à l’étude de certaines équations différentielles ordinaires. J Math Pures Appl 9:217–272
Pulay P (1980) Convergence acceleration of iterative sequences. the case of scf iteration. Chem Phys Lett 73:393–398. https://doi.org/10.1016/0009-2614(80)80396-4
Ramaniah LM, Bernasconi M, Parrinello M (1998) Density-functional study of hydration of sodium in water clusters. J Chem Phys 109:6839–6843. https://doi.org/10.1063/1.477250
Wessing S (2019) Proper initialization is crucial for the Nelder-Mead simplex search. Optim Lett 13:847–856. https://doi.org/10.1007/s11590-018-1284-4
Yin ZY, Jin YF, Shen JS, Hicher PY (2018) Optimization techniques for identifying soil parameters in geotechnical engineering: comparative study and enhancement. Int J Numer Anal Methods Geomech 42:70–94. https://doi.org/10.1002/nag.2714