Zero-inertia limit: from particle swarm optimization to consensus-based optimization. (English) Zbl 1500.90088
Summary: Recently a continuous description of particle swarm optimization (PSO) based on a system of stochastic differential equations was proposed by S. Grassi and L. Pareschi [Math. Models Methods Appl. Sci. 31, No. 8, 1625–1657 (2021; Zbl 1473.35570)] where the authors formally showed the link between PSO and the consensus-based optimization (CBO) through the zero-inertia limit. This paper is devoted to solving this theoretical open problem proposed in [loc. cit.] by providing a rigorous derivation of CBO from PSO through the limit of zero inertia, and a quantified convergence rate is obtained as well. The proofs are based on a probabilistic approach by investigating both the weak and strong convergence of the corresponding stochastic differential equations of Mckean type in the continuous path space and the results are illustrated with some numerical examples.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
Citations:
Zbl 1473.35570References:
| [1] | E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, Wiley, New York, 1989. · Zbl 0674.90059 |
| [2] | D. Aldous, Stopping times and tightness, Ann. Probab., 6 (1978), pp. 335-340. · Zbl 0391.60007 |
| [3] | L. Ambrosio, N. Gigli, and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer, Basel, Switzerland, 2008, https://doi.org/10.1007/b137080. · Zbl 1145.35001 |
| [4] | T. Back, D. B. Fogel, and Z. Michalewicz, eds., Handbook of Evolutionary Computation, 1st ed., IOP Publishing, Bristol, UK, 1997. · Zbl 0883.68001 |
| [5] | N. Bellomo, A. Bellouquid, and D. Knopoff, From the microscale to collective crowd dynamics, Multiscale Model. Simul., 11 (2013), pp. 943-963. · Zbl 1280.90019 |
| [6] | N. Bellomo and C. Dogbe, On the modeling of traffic and crowds: A survey of models, speculations, and perspectives, SIAM Rev., 53 (2011), pp. 409-463. · Zbl 1231.90123 |
| [7] | P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1999. · Zbl 0944.60003 |
| [8] | C. Blum and A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Comput. Surv., 35 (2003), pp. 268-308, https://doi.org/10.1145/937503.937505. |
| [9] | F. Bolley, J. A. Canizo, and J. A. Carrillo, Stochastic mean-field limit: Non-Lipschitz forces and swarming, Math. Models Methods Appl. Sci., 21 (2011), pp. 2179-2210, https://doi.org/10.1142/s0218202511005702. · Zbl 1273.82041 |
| [10] | V. Bruned, A. Mas, and S. Wlodarczyk, Weak Convergence of Particle Swarm Optimization, preprint, arXiv:1811.04924, 2018. |
| [11] | J. A. Carrillo and Y.-P. Choi, Quantitative error estimates for the large friction limit of Vlasov equation with nonlocal forces, in Ann. Inst. H. Poincaré Anal. Non Linéaire, 37 (2020), pp. 925-954. · Zbl 1440.35322 |
| [12] | J. A. Carrillo, Y.-P. Choi, and S. Salem, Propagation of chaos for the Vlasov-Poisson-Fokker-Planck equation with a polynomial cut-off, Commun. Contemp. Math., 21 (2019), 1850039, https://doi.org/10.1142/s0219199718500396. · Zbl 1417.35201 |
| [13] | J. A. Carrillo, Y.-P. Choi, C. Totzeck, and O. Tse, An analytical framework for consensus-based global optimization method, Math. Models Methods Appl. Sci., 28 (2018), pp. 1037-1066, https://doi.org/10.1142/s0218202518500276. · Zbl 1397.35311 |
| [14] | J. A. Carrillo, M. Fornasier, J. Rosado, and G. Toscani, Asymptotic flocking dynamics for the kinetic Cucker-Smale model, SIAM J. Math. Anal., 42 (2010), pp. 218-236. · Zbl 1223.35058 |
| [15] | J. A. Carrillo, S. Jin, L. Li, and Y. Zhu, A consensus-based global optimization method for high dimensional machine learning problems, ESAIM Control Optim. Calc. Vari., 27 (2021), 55 https://doi.org/10.1051/cocv/2020046, 2019. · Zbl 1480.60195 |
| [16] | Y.-P. Choi and O. Tse, Quantified Overdamped Limit for Kinetic Vlasov-Fokker-Planck Equations with Singular Interaction Forces, preprint, arXiv:2012.00422, 2020. · Zbl 1506.35236 |
| [17] | F. Cucker and S. Smale, Emergent behavior in flocks, IEEE Trans. Automat. Control, 52 (2007), pp. 852-862. · Zbl 1366.91116 |
| [18] | G. Da Prato and J. Zabczyk, Stochastic Equations in Infinite Dimensions, Cambridge University Press, Cambridge, 2014. · Zbl 1317.60077 |
| [19] | A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, Berlin, 2010, https://doi.org/10.1007/978-3-642-03311-7. · Zbl 1177.60035 |
| [20] | M. H. Duong, A. Lamacz, M. A. Peletier, and U. Sharma, Variational approach to coarse-graining of generalized gradient flows, Calc. Var. Partial Differential Equations, 56 (2017), pp. 1-65. · Zbl 1444.35107 |
| [21] | R. Fetecau and W. Sun, First-order aggregation models and zero inertia limits, J. Differential Equations, 259 (2015), pp. 6774-6802. · Zbl 1329.35320 |
| [22] | M. Fornasier, H. Huang, L. Pareschi, and P. Sünnen, Consensus-based optimization on hypersurfaces: Well-posedness and mean-field limit, Math. Models Methods Appl. Sci., 30 (2020), pp. 2725-2751, https://doi.org/10.1142/S0218202520500530. · Zbl 1467.90039 |
| [23] | M. Fornasier, H. Huang, L. Pareschi, and P. Sünnen, Anisotropic diffusion in consensus-based optimization on the sphere, SIAM J. Optimiz., to appear. · Zbl 1467.90039 |
| [24] | M. Fornasier, H. Huang, L. Pareschi, and P. Sünnen, Consensus-based optimization on the sphere: Convergence to global minimizers and machine learning, J. Mach. Learn. Res., 22 (2021), pp. 1-55. · Zbl 07626752 |
| [25] | M. Fornasier, T. Klock, and K. Riedl, Consensus-Based Optimization Methods Converge Globally in Mean-field Law, preprint, arXiv:2103.15130, 2021. |
| [26] | M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics, 2nd ed., Springer, New York, 2010. · Zbl 1198.90002 |
| [27] | S. Grassi and L. Pareschi, From particle swarm optimization to consensus based optimization: Stochastic modeling and mean-field limit, Math. Models Methods Appl. Sci., 31 (2021), pp. 1625-1657. · Zbl 1473.35570 |
| [28] | S.-Y. Ha, S. Jin, and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci., 30 (2020), pp. 2417-2444, https://doi.org/10.1142/S0218202520500463. · Zbl 1467.90040 |
| [29] | S.-Y. Ha and E. Tadmor, From particle to kinetic and hydrodynamic descriptions of flocking, Kinet. Relat. Models, 1 (2008), pp. 415-435. · Zbl 1402.76108 |
| [30] | D. D. Holm and V. Putkaradze, Formation of clumps and patches in self-aggregation of finite-size particles, Phys. D, 220 (2006), pp. 183-196. · Zbl 1125.82021 |
| [31] | H. Huang, A note on the mean-field limit for the particle swarm optimization, Appl. Math. Lett., 117 (2021), 107133. · Zbl 1475.82015 |
| [32] | H. Huang, J.-G. Liu, and P. Pickl, On the mean-field limit for the Vlasov-Poisson-Fokker-Planck system, J. Stat. Phys., 181 (2020), pp. 1915-1965, https://doi.org/10.1007/s10955-020-02648-3. · Zbl 1466.35344 |
| [33] | H. Huang and J. Qiu, On the mean-field limit for the consensus-based optimization, Math. Methods Appl. Sci., (2022), pp. 1-18, https://doi.org/10.1002/mma.8279. |
| [34] | N. Ikeda and S. Watanabe, Stochastic Differential Equations and Diffusion Processes, Elsevier, Amsterdam, 1989. · Zbl 0684.60040 |
| [35] | P.-E. Jabin, Macroscopic limit of Vlasov type equations with friction, in Ann. Inst. H. Poincaré (C) Non Linear Anal., 17 (2000), pp. 651-672. · Zbl 0965.35013 |
| [36] | P.-E. Jabin and Z. Wang, Mean field limit for stochastic particle systems, in Active Particles, Vol. 1, Springer, Cham, Switzerland, 2017, pp. 379-402, https://doi.org/10.1007/978-3-319-49996-3_10. |
| [37] | J. Jacod and A. Shiryaev, Limit Theorems for Stochastic Processes, Grundlehren Math. Wiss. 288, Springer, New York, 2002. · Zbl 0635.60021 |
| [38] | J. Kennedy, The particle swarm: Social adaptation of knowledge, in Proceedings of 1997 IEEE International Conference on Evolutionary Computation, IEEE, Piscataway, NJ, 1997, pp. 303-308, https://doi.org/10.1109/ICEC.1997.592326. |
| [39] | J. Kennedy and R. Eberhart, Particle swarm optimization, in Proceedings of 1995 IEEE International Conference on Neural Networks, Vol. 4, IEEE, Piscataway, NJ, 1995, pp. 1942-1948, https://doi.org/10.1109/ICNN.1995.488968. |
| [40] | J. Kim, M. Kang, D. Kim, S.-Y. Ha, and I. Yang, A stochastic consensus method for nonconvex optimization on the Stiefel manifold, in Proceedings of the 2020 59th IEEE Conference on Decision and Control (CDC), IEEE, Piscataway, NJ, 2020, pp. 1050-1057. |
| [41] | H. A. Kramers, Brownian motion in a field of force and the diffusion model of chemical reactions, Physica, 7 (1940), pp. 284-304. · Zbl 0061.46405 |
| [42] | N. V. Krylov, Controlled Diffusion Processes, Stochastic Model. Appl. Probab. 14, Springer, Berlin, 2008. |
| [43] | S.-W. Lin, K.-C. Ying, S.-C. Chen, and Z.-J. Lee, Particle swarm optimization for parameter determination and feature selection of support vector machines, Expert Systems Appl., 35 (2008), pp. 1817-1824. |
| [44] | X. Mao, Stochastic Differential Equations and Applications, Harwood, Chichester, UK, 2007. · Zbl 1138.60005 |
| [45] | P. D. Miller, Applied Asymptotic Analysis, Grad. Stud. Math. 75, American Mathematical Society, Providence, RI, 2006, https://doi.org/10.1090/gsm/075. · Zbl 1101.41031 |
| [46] | S. Motsch and E. Tadmor, Heterophilious dynamics enhances consensus, SIAM Rev., 56 (2014), pp. 577-621. · Zbl 1310.92064 |
| [47] | R. Pinnau, C. Totzeck, O. Tse, and S. Martin, A consensus-based model for global optimization and its mean-field limit, Math. Models Methods Appl. Sci., 27 (2017), pp. 183-204, https://doi.org/10.1142/s0218202517400061. · Zbl 1388.90098 |
| [48] | R. Poli, Mean and variance of the sampling distribution of particle swarm optimizers during stagnation, IEEE Trans. Evol. Comput., 13 (2009), pp. 712-721. |
| [49] | R. Poli, J. Kennedy, and T. Blackwell, Particle swarm optimization, Swarm Intell., 1 (2007), pp. 33-57, https://doi.org/10.1007/s11721-007-0002-0. |
| [50] | M. Schmitt and R. Wanka, Particle swarm optimization almost surely finds local optima, Theoret. Comput. Sci., 561 (2015), pp. 57-72. · Zbl 1303.68125 |
| [51] | Y. Shi and R. Eberhart, A modified particle swarm optimizer, in Proceedings of 1998 IEEE International Conference on Evolutionary Computation, IEEE, Piscataway, NJ, 1998, pp. 69-73, https://doi.org/10.1109/ICEC.1998.699146. |
| [52] | A.-S. Sznitman, Topics in propagation of chaos, in Ecole d’été de probabilités de Saint-Flour XIX-1989, Springer, Berlin, 1991, pp. 165-251, https://doi.org/10.1007/bfb0085169. · Zbl 0732.60114 |
| [53] | F. Van den Bergh and A. P. Engelbrecht, A convergence proof for the particle swarm optimiser, Fund. Inform., 105 (2010), pp. 341-374. · Zbl 1211.90320 |
| [54] | Y. Zhang, S. Wang, and G. Ji, A comprehensive survey on particle swarm optimization algorithm and its applications, Math. Probl. Eng., 2015 (2015). · Zbl 1394.90588 |
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.
