Multistart with early termination of descents. (English) Zbl 1465.90083
Summary: 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.
MSC:
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Hartman, J., Some experiments in global optimization, Naval Res. Q., 20, 569-576 (1973) · Zbl 0265.90048 · doi:10.1002/nav.3800200316 |
| [2] | 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) · Zbl 1192.62180 |
| [3] | Johnson, NL; Kotz, S.; Balakrishnan, N., Discrete Multivariate Distributions (1997), New York: Wiley, New York · Zbl 0868.62048 |
| [4] | Krityakierne, T.; Shoemaker, CA, Soms: Surrogate multistart algorithm for use with nonlinear programming for global optimization, Int. Trans. Oper. Res., 24, 5, 1139-1172 (2017) · Zbl 1371.90110 · doi:10.1111/itor.12190 |
| [5] | 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) · doi:10.1016/j.eswa.2017.02.048 |
| [6] | Lozano, M.; Rodriguez, FJ; 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) · doi:10.1016/j.engappai.2016.01.037 |
| [7] | Pepelyshev, A.; Zhigljavsky, A.; Žilinskas, A., Performance of global random search algorithms for large dimensions, J. Global Optim., 71, 57-71 (2018) · Zbl 1402.90135 · doi:10.1007/s10898-017-0535-8 |
| [8] | Peri, D., Tinti, F.: A multistart gradient-based algorithm with surrogate model for global optimization. Commun. Appl. Ind. Math. 3(1) (2012) · Zbl 1329.90110 |
| [9] | Pronzato, L.; Wynn, HP; Zhigljavsky, AA, Dynamical Search: Applications of Dynamical Systems in Search and Optimization (1999), Boca Raton: CRC Press, Boca Raton · Zbl 1053.90102 |
| [10] | Ruder, S.: An overview of gradient descent optimization algorithms. arXiv:1609.04747 (2016) |
| [11] | 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) |
| [12] | Törn, A.; Žilinskas, A., Global Optimization (1989), New York: Springer, New York · Zbl 0752.90075 · doi:10.1007/3-540-50871-6 |
| [13] | Tu, W.; Mayne, W., Studies of multi-start clustering for global optimization, Int. J. Numer. Methods Eng., 53, 2239-2252 (2002) · Zbl 0995.65065 · doi:10.1002/nme.400 |
| [14] | Zhigljavsky, A.; Žilinskas, A., Stochastic Global Optimization (2008), New York: Springer, New York · Zbl 1136.90003 |
| [15] | Zieliński, R., A statistical estimate of the structure of multi-extremal problems, Math. Program., 21, 1, 348-356 (1981) · Zbl 0476.90086 · doi:10.1007/BF01584254 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
