In this paper, we propose a K-means clustering-based integral level-value estimation algorithm tosolveakindof box-constrainedglobal optimizationproblem. For this purpose, we introduce the generalized variance function associated with the level-value of the objective function to be minimized. The variance function has a good property when Newton's method is used to solve a variance equation resulting by setting the variance function to zero. We prove that the largest root of the variance equation is equal to the global minimum value of the corresponding optimization problem. Based on the K-means clustering algorithm, the multiple importance sampling technique is proposed in the implementable algorithm. The main idea of the cross-entropy method is used to update the parameters of sampling density function. The asymptotic convergence of the algorithm is proved, and the validity of the algorithm is verified by numerical experiments.
Chen Wang, Dong-Hua Wu
. A K-Means Clustering-Based Multiple Importance Sampling Algorithm for Integral Global Optimization[J]. Journal of the Operations Research Society of China, 2023
, 11(1)
: 157
-176
.
DOI: 10.1007/s40305-021-00353-w
[1] Pardalos, P.M., Romeijn, H., Tuy, H.:Recent developments and trends in global optimization.J.Comput.Appl.Math.124, 209-228(2000)
[2] Gao, S.J., de Silva, C.W.:Estimation distribution algorithms on constrained optimization problems.Appl.Math.Comput.339, 323-345(2018)
[3] Zheng, Q.:Robust analysis and global optimization.Ann.Oper.Res.24, 273-286(1990)
[4] Chew, S., Zheng, Q.:Integral Global Optimization.Theory, Implementation and Applications.Springer, Berlin (1988)
[5] Tian, W.W., Wu, D.H., et al.:Modified integral-level set method for the constrained global optimization.Appl.Math.Mech.25(2), 202-210(2004)
[6] Phu, H.X., Hoffmann, A.:Essential supremum and supremum of summable functions.Numer.Funct.Anal.Optim.17(1-2), 167-180(1996)
[7] Wu, D.H., Yu, W., Tian, W.W.:A level-value estimation method for solving global optimization.Appl.Math.Mech.27, 1001-1010(2006)
[8] Yu, H.B., Zeng, W.J., Wu, D.H.:A stochastic level-value estimation method for global optimization.J.Oper.Res.Soc.China 6, 1-16(2017)
[9] Peng, Z., Wu, D.H., Zheng, Q.:A level-value estimation method and stochastic implementation for global optimization.J.Optim.Theory Appl.156(2), 493-523(2013)
[10] Peng, Z., Wu, D.H., Tian, W.W.:A level-value estimation method for solving constrained global optimization.Math.Numer.Sin.29(3), 293-304(2007)
[11] Xie, H.L., et al.:Improving K-means clustering with enhanced Firefly Algorithms.Appl.Soft Comput.84(2019)
[12] Meila, M.:The uniqueness of a good optimum for k-means.Mach.Learn.625-632(2006)
[13] Jain, Anil K.:Data clustering:50 years beyond K-means.Int.Conf.Pattern Recognit.31(8), 651-666(2010)
[14] Rubinstein, R.Y.:The cross-entropy method for combinatorial and continuous optimization.Methodol.Comput.Appl.Probab.8, 383-407(2006)
[15] Kroese, D.P., Porotsky, S., Rubinstein, R.Y.:The cross-entropy method for continuous multi-extremal optimization.Methodol.Comput.Appl.Probab.2, 127-190(1999)
[16] Qian,M.P.,Gong,G.L.:Applied Stochastic Process, pp.186-188.TsingHuaUniversity Press, Beijing (2007)
[17] Zhou, X.Y.,Wang, K.,Wu, D.H.,Wang, C.:Cross entropy algorithm with multiple important sample level estimation for global optimization problems.Oper.Res.Trans.23(1), 15-27(2019)
