Multistart with early termination of descents
Tóm tắt
Multistart is a celebrated global optimization technique frequently applied in practice. In its pure form, multistart has low efficiency. However, the simplicity of multistart and multitude of possibilities of its generalization make it very attractive especially in high-dimensional problems where e.g. Lipschitzian and Bayesian algorithms are not applicable. We propose a version of multistart where most of the local descents are terminated very early; we will call it METOD as an abbreviation for multistart with early termination of descents. The performance of the proposed algorithm is demonstrated on randomly generated test functions with 100 variables and a modest number of local minimizers.
Tài liệu tham khảo
Hartman, J.: Some experiments in global optimization. Naval Res. Q. 20, 569–576 (1973)
Haycroft, R., Pronzato, L., Wynn, H.P., Zhigljavsky, A.: Studying convergence of gradient algorithms via optimal experimental design theory. In: Optimal Design and Related Areas in Optimization and Statistics, pp. 13–37. Springer, New York (2009)
Johnson, N.L., Kotz, S., Balakrishnan, N.: Discrete Multivariate Distributions. Wiley, New York (1997)
Krityakierne, T., Shoemaker, C.A.: Soms: Surrogate multistart algorithm for use with nonlinear programming for global optimization. Int. Trans. Oper. Res. 24(5), 1139–1172 (2017)
López-Soto, D., Angel-Bello, F., Yacout, S., Alvarez, A.: A multi-start algorithm to design a multi-class classifier for a multi-criteria ABC inventory classification problem. Expert Syst. Appl. 81, 12–21 (2017)
Lozano, M., Rodriguez, F.J., Peralta, D., García-Martínez, C.: Randomized greedy multi-start algorithm for the minimum common integer partition problem. Eng. Appl. Artif. Intell. 50, 226–235 (2016)
Pepelyshev, A., Zhigljavsky, A., Žilinskas, A.: Performance of global random search algorithms for large dimensions. J. Global Optim. 71, 57–71 (2018)
Peri, D., Tinti, F.: A multistart gradient-based algorithm with surrogate model for global optimization. Commun. Appl. Ind. Math. 3(1) (2012)
Pronzato, L., Wynn, H.P., Zhigljavsky, A.A.: Dynamical Search: Applications of Dynamical Systems in Search and Optimization. CRC Press, Boca Raton (1999)
Ruder, S.: An overview of gradient descent optimization algorithms. arXiv:1609.04747 (2016)
Taubman, D., Zakhor, A.: A multi-start algorithm for signal adaptive subband systems (image coding). In: [Proceedings] ICASSP-92: 1992 IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3, pp. 213–216. IEEE (1992)
Törn, A., Žilinskas, A.: Global Optimization. Springer, New York (1989)
Tu, W., Mayne, W.: Studies of multi-start clustering for global optimization. Int. J. Numer. Methods Eng. 53, 2239–2252 (2002)
Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008)
Zieliński, R.: A statistical estimate of the structure of multi-extremal problems. Math. Program. 21(1), 348–356 (1981)