×

Anisotropic diffusion in consensus-based optimization on the sphere. (English) Zbl 1509.65047

Summary: In this paper, we are concerned with the global minimization of a possibly nonsmooth and nonconvex objective function constrained on the unit hypersphere by means of a multi-agent derivative-free method. The proposed algorithm falls into the class of the recently introduced consensus-based optimization. In fact, agents move on the sphere driven by a drift towards an instantaneous consensus point, which is computed as a convex combination of agent locations, weighted by the cost function according to Laplace’s principle, and it represents an approximation to a global minimizer. The dynamics is further perturbed by an anisotropic random vector field to favor exploration. The main results of this paper are about the proof of convergence of the numerical scheme to global minimizers provided conditions of well-preparation of the initial datum. The proof of convergence combines a mean-field limit result with a novel asymptotic analysis and classical convergence results of numerical methods for stochastic differential equations. The main innovation with respect to previous work is the introduction of an anisotropic stochastic term, which allows us to ensure the independence of the parameters of the algorithm from the dimension and to scale the method to work in very high dimension. We present several numerical experiments, which show that the algorithm proposed in the present paper is extremely versatile and outperforms previous formulations with isotropic stochastic noise.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
35Q90 PDEs in connection with mathematical programming
35Q84 Fokker-Planck equations

References:

[1] P.-A. Absil and S. Hosseini, A collection of nonsmooth Riemannian optimization problems, in Nonsmooth Riemannian Optimization Problems, Internat. Ser. Numer. Math. 170, Birkhäuser/Springer, Cham, 2019, pp. 1-15. · Zbl 1423.49012
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043
[3] G. Albi, Y.-P. Choi, M. Fornasier, and D. Kalise, Mean field control hierarchy, Appl. Math. Optim., 76 (2017), pp. 93-135. · Zbl 1378.49024
[4] G. Albi and L. Pareschi, Binary interaction algorithms for the simulation of flocking and swarming dynamics, Multiscale Model. Simul., 11 (2013), pp. 1-29, https://doi.org/10.1137/120868748. · Zbl 1274.92053
[5] W. A. Bainbridge, P. Isola, and A. Oliva, The intrinsic memorability of face photographs, J. Exp. Psychol. Gen., 142 (2013), pp. 1323-1334.
[6] A. S. Bandeira, K. Scheinberg, and L. N. Vicente, Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization, Math. Program., 134 (2012), pp. 223-257. · Zbl 1254.65072
[7] T. Bendory, S. Dekel, and A. Feuer, Super-resolution on the sphere using convex optimization, IEEE Trans. Signal Process., 63 (2015), pp. 2253-2262. · Zbl 1394.94072
[8] E. Candès, X. Li, and M. Soltanolkotabi, Phase retrieval via Wirtinger flow: Theory and algorithms, IEEE Trans. Inform. Theory, 61 (2015), pp. 1985-2007. · Zbl 1359.94069
[9] E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski, Phase retrieval via matrix completion, SIAM J. Imaging Sci., 6 (2013), pp. 199-225, https://doi.org/10.1137/110848074. · Zbl 1280.49052
[10] 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. · Zbl 1397.35311
[11] 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. Var., 27 (2021), S5. · Zbl 1480.60195
[12] R. Chandra, Z. Zhong, J. Hontz, V. McCulloch, C. Studer, and T. Goldstein, Phase-Pack: A phase retrieval library, in 2017 51st Asilomar Conference on Signals, Systems, and Computers, 2017, pp. 1617-1621.
[13] X. Chen and R. S. Womersley, Spherical designs and nonconvex minimization for recovery of sparse signals on the sphere, SIAM J. Imaging Sci., 11 (2018), pp. 1390-1415, https://doi.org/10.1137/17M1147378. · Zbl 1401.90167
[14] Y. Chen, Y. Chi, J. Fan, and C. Ma, Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval, Math. Program., 176 (2019), pp. 5-37. · Zbl 1415.90086
[15] C. Cipriani, H. Huang, and J. Qiu, Zero-inertia limit: From particle swarm optimization to consensus-based optimization, SIAM J. Math. Anal., 54 (2022), pp. 3091-3121, https://doi.org/10.1137/21M1412323. · Zbl 1500.90088
[16] A. R. Conn, K. Scheinberg, and L. N. Vicente, Introduction to Derivative-Free Optimization, SIAM, Philadelphia, 2009, https://doi.org/10.1137/1.9780898718768. · Zbl 1163.49001
[17] I. D. Couzin, J. Krause, R. James, G. D. Ruxton, and N. R. Franks, Collective memory and spatial sorting in animal groups, J. Theoret. Biol., 218 (2002), pp. 1-11.
[18] P. Degond and S. Motsch, Continuum limit of self-driven particles with orientation interaction, Math. Models Methods Appl. Sci., 18 (2008), pp. 1193-1215. · Zbl 1157.35492
[19] M. Dorigo and C. Blum, Ant colony optimization theory: A survey, Theoret. Comput. Sci., 344 (2005), pp. 243-278. · Zbl 1154.90626
[20] R. Durrett, Stochastic Calculus: A Practical Introduction, CRC Press, Boca Raton, FL, 2018. · Zbl 0856.60002
[21] R. C. Fetecau, H. Huang, and W. Sun, Propagation of chaos for the Keller-Segel equation over bounded domains, J. Differential Equations, 266 (2019), pp. 2142-2174. · Zbl 1421.35381
[22] C. Fiedler, M. Fornasier, T. Klock, and M. Rauchensteiner, Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples, preprint, https://arxiv.org/abs/2101.07150, 2021.
[23] J. Fienup, Phase retrieval algorithms: A comparison, Appl. Opt., 21 (1982), pp. 2758-2769.
[24] 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. · Zbl 1467.90039
[25] 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
[26] A. Frouvelle and J.-G. Liu, Dynamics in a kinetic model of oriented particles with phase transition, SIAM J. Math. Anal., 44 (2012), pp. 791-826, https://doi.org/10.1137/110823912. · Zbl 1248.35097
[27] R. W. Gerchberg and W. O. Saxton, Practical algorithm for determination of phase from image and diffraction plane pictures, OPTIK, 35 (1972), pp. 237-246.
[28] D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer, Berlin, 2015. · Zbl 1042.35002
[29] 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
[30] S.-Y. Ha, S. Jin, and D. Kim, Convergence and error estimates for time-discrete consensus-based optimization algorithms, Numer. Math., 147 (2021), pp. 255-282. · Zbl 1467.65064
[31] D. J. Higham, X. Mao, and A. M. Stuart, Strong convergence of Euler-type methods for nonlinear stochastic differential equations, SIAM J. Numer. Anal., 40 (2002), pp. 1041-1063, https://doi.org/10.1137/S0036142901389530. · Zbl 1026.65003
[32] H. Huang and J. Qiu, On the mean-field limit for the consensus-based optimization, Math. Methods Appl. Sci., to appear. · Zbl 1527.60077
[33] M. Jamil and X.-S. Yang, A literature survey of benchmark functions for global optimization problems, Int. J. Math. Model. Numer. Optim., 4 (2013), pp. 150-194. · Zbl 1280.65053
[34] S. Jin, L. Li, and J.-G. Liu, Random batch methods (RBM) for interacting particle systems, J. Comput. Phys., 400 (2020), 108877. · Zbl 1453.82065
[35] I. N. Katz and L. Cooper, Optimal location on a sphere, Comput. Math. Appl., 6 (1980), pp. 175-196. · Zbl 0451.65046
[36] J. Kennedy, Particle swarm optimization, in Encyclopedia of Machine Learning, Springer, Boston, 2011, pp. 760-766.
[37] J. Kileel and J. M. Pereira, Subspace Power Method for Symmetric Tensor Decomposition and Generalized PCA, preprint, https://arxiv.org/abs/1912.04007, 2019.
[38] 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 59th Annual IEEE Conference on Decision and Control (CDC), 2020, pp. 1050-1057.
[39] J. Larson, M. Menickelly, and S. M. Wild, Derivative-free optimization methods, Acta Numer., 28 (2019), p. 287-404. · Zbl 1461.65169
[40] G. Lerman and T. Maunu, Fast, robust and non-convex subspace recovery, Inf. Inference, 7 (2017), pp. 277-336. · Zbl 1476.90262
[41] G. Lerman, M. B. McCoy, J. A. Tropp, and T. Zhang, Robust computation of linear models by convex relaxation, Found. Comput. Math., 15 (2015), pp. 363-410. · Zbl 1328.62377
[42] M. Marazzi and J. Nocedal, Wedge trust region methods for derivative free optimization, Math. Program., 91 (2002), pp. 289-305. · Zbl 1049.90134
[43] G. Marsaglia, Choosing a point from the surface of a sphere, Ann. Math. Statist., 43 (1972), pp. 645-646. · Zbl 0248.65008
[44] T. Maunu, T. Zhang, and G. Lerman, A well-tempered landscape for non-convex robust subspace recovery, J. Mach. Learn. Res., 20 (2019), 37. · Zbl 1484.62063
[45] M. E. Muller, A note on a method for generating points uniformly on n-dimensional spheres, Commun. ACM, 2 (1959), pp. 19-20. · Zbl 0086.11605
[46] J. A. Nelder and R. Mead, A simplex method for function minimization, Comput. J., 7 (1965), pp. 308-313. · Zbl 0229.65053
[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. · Zbl 1388.90098
[48] E. Platen, An introduction to numerical methods for stochastic differential equations, Acta Numer., 8 (1999), pp. 197-246. · Zbl 0942.65004
[49] R. Poli, J. Kennedy, and T. Blackwell, Particle swarm optimization, Swarm Intell., 1 (2007), pp. 33-57.
[50] M. J. D. Powell, UOBYQA: Unconstrained optimization by quadratic approximation, Math. Program., 92 (2002), pp. 555-582. · Zbl 1014.65050
[51] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), pp. 1302-1324. · Zbl 1125.15014
[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. · Zbl 0732.60114
[53] C. Totzeck and M. Wolfram, Consensus-based global optimization with personal best, Math. Biosci. Eng., 17 (2020), pp. 6026-6044. · Zbl 1473.90132
[54] T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett., 75 (1995), pp. 1226-1229.
[55] Z. Zhang, Sobolev seminorm of quadratic functions with applications to derivative-free optimization, Math. Program., 146 (2014), pp. 77-96. · Zbl 1315.90063
[56] G. zhen Yang, B. zhen Dong, B. yuan Gu, J. yao Zhuang, and O. K. Ersoy, Gerchberg-Saxton and Yang-Gu algorithms for phase retrieval in a nonunitary transform system: A comparison, Appl. Opt., 33 (1994), pp. 209-218.
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.