Adaptive State-Dependent Diffusion for Derivative-Free Optimization

doi:10.1007/s42967-023-00324-3

Communications on Applied Mathematics and Computation ›› 2024, Vol. 6 ›› Issue (2): 1241-1269.doi: 10.1007/s42967-023-00324-3

• ORIGINAL PAPERS • 上一篇下一篇

Adaptive State-Dependent Diffusion for Derivative-Free Optimization

Bj?rn Engquist¹, Kui Ren², Yunan Yang³

1. Department of Mathematics and the Oden Institute, The University of Texas, Austin, TX 78712, USA;
2. Department of Applied Physics and Applied Mathematics, Columbia University, New York, NY 10027, USA;
3. Department of Mathematics, Cornell University, Ithaca, NY 14853, USA

收稿日期:2023-02-09 修回日期:2023-09-14 接受日期:2023-09-17 出版日期:2024-01-09 发布日期:2024-01-09
通讯作者: Yunan Yang,E-mail:yunan.yang@cornell.edu;Bj?rn Engquist,E-mail:engquist@oden.utexas.edu;Kui Ren,E-mail:kr2002@columbia.edu E-mail:yunan.yang@cornell.edu;engquist@oden.utexas.edu;kr2002@columbia.edu
基金资助:
This work is partially supported by the National Science Foundation through grants DMS-2208504 (BE), DMS-1913309 (KR), DMS-1937254 (KR), and DMS-1913129 (YY).

Adaptive State-Dependent Diffusion for Derivative-Free Optimization

Bj?rn Engquist¹, Kui Ren², Yunan Yang³

1. Department of Mathematics and the Oden Institute, The University of Texas, Austin, TX 78712, USA;
2. Department of Applied Physics and Applied Mathematics, Columbia University, New York, NY 10027, USA;
3. Department of Mathematics, Cornell University, Ithaca, NY 14853, USA

Received:2023-02-09 Revised:2023-09-14 Accepted:2023-09-17 Online:2024-01-09 Published:2024-01-09
Contact: Yunan Yang,E-mail:yunan.yang@cornell.edu;Bj?rn Engquist,E-mail:engquist@oden.utexas.edu;Kui Ren,E-mail:kr2002@columbia.edu E-mail:yunan.yang@cornell.edu;engquist@oden.utexas.edu;kr2002@columbia.edu
Supported by:
This work is partially supported by the National Science Foundation through grants DMS-2208504 (BE), DMS-1913309 (KR), DMS-1937254 (KR), and DMS-1913129 (YY).

摘要/Abstract

摘要： This paper develops and analyzes a stochastic derivative-free optimization strategy. A key feature is the state-dependent adaptive variance. We prove global convergence in probability with algebraic rate and give the quantitative results in numerical examples. A striking fact is that convergence is achieved without explicit information of the gradient and even without comparing different objective function values as in established methods such as the simplex method and simulated annealing. It can otherwise be compared to annealing with state-dependent temperature.

关键词: Derivative-free optimization, Global optimization, Adaptive diffusion, Stationary distribution, Fokker-Planck theory

Abstract: This paper develops and analyzes a stochastic derivative-free optimization strategy. A key feature is the state-dependent adaptive variance. We prove global convergence in probability with algebraic rate and give the quantitative results in numerical examples. A striking fact is that convergence is achieved without explicit information of the gradient and even without comparing different objective function values as in established methods such as the simplex method and simulated annealing. It can otherwise be compared to annealing with state-dependent temperature.

Key words: Derivative-free optimization, Global optimization, Adaptive diffusion, Stationary distribution, Fokker-Planck theory

Bj?rn Engquist, Kui Ren, Yunan Yang. Adaptive State-Dependent Diffusion for Derivative-Free Optimization[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1241-1269.

参考文献

[1] Alarie, S., Audet, C., Gheribi, A.E., Kokkolaras, M., Le Digabel, S.: Two decades of blackbox optimization applications. EURO J. Comput. Optim. 9, 100011 (2021)
[2] Carrillo, J.A., Jin, S., Li, L., Zhu, Y.: A consensus-based global optimization method for high dimensional machine learning problems. ESAIM Control Optim. Calc. Var. 27, S5 (2021)
[3] Cartis, C., Roberts, L.: Scalable subspace methods for derivative-free nonlinear least-squares optimization. Math. Program. 199, 461-524 (2023)
[4] Chen, L., Stroock, D.W.: The fundamental solution to the Wright-Fisher equation. SIAM J. Math. Anal. 42, 539-567 (2010)
[5] Chiang, T.-S., Hwang, C.-R., Sheu, S.J.: Diffusion for global optimization in $\mathbb{R}^n$. SIAM J. Control. Optim. 25(3), 737-753 (1987)
[6] Chow, S.-N., Yang, T.-S., Zhou, H.-M.: Global optimizations by intermittent diffusion. In: Chaos, CNN, Memristors and Beyond: a Festschrift for Leon Chua With DVD-ROM, composed by Eleonora Bilotta, pp. 466-479. World Scientific (2013)
[7] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-free Optimization. SIAM, Philadelphia (2009)
[8] Dekkers, A., Aarts, E.: Global optimization and simulated annealing. Math. Program. 50(1), 367-393 (1991)
[9] Engquist, B., Ren, K., Yang, Y.: An algebraically converging stochastic gradient descent algorithm for global optimization. arXiv:2204.05923 (2022)
[10] Epstein, C.L., Mazzeo, R.: Wright-Fisher diffusion in one dimension. SIAM J. Math. Anal. 42, 568-608 (2010)
[11] Fabes, E.B., Kenig, C.E., Serapioni, R.P.: The local regularity of solutions of degenerate elliptic equations. Commun. Stat. Theory Methods 7(1), 77-116 (1982)
[12] Fornasier, M., Klock, T., Riedl, K:. Consensus-based optimization methods converge globally. arXiv:2103.15130v4 (2021)
[13] Fragnelli, G., Mugnai, D.: Carleman estimates, observability inequalities and null controllability for interior degenerate non smooth parabolic equations. Memoirs of the American Mathematical Society, 242(1146) (2016)
[14] Fragnelli, G., Ruiz Goldstein, G., Goldstein, J.A., Romanelli, S.: Generators with interior degeneracy on spaces of l² type. Electron. J. Differ. Equ. 2012, 1-30 (2012)
[15] Frederick, C., Egerstedt, M., Zhou, H.: Collective motion planning for a group of robots using intermittent diffusion. J. Sci. Comput. 90(1), 1-20 (2022)
[16] Gelfand, S.B., Mitter, S.K.: Recursive stochastic algorithms for global optimization in $\mathbb{R}^d$. SIAM J. Control. Optim. 29, 999-1018 (1991)
[17] Geman, S., Hwang, C.-R.: Diffusions for global optimization. SIAM J. Control. Optim. 24, 1031-1043 (1986)
[18] Haupt, R.L., Haupt, S.E.: Practical Genetic Algorithms. Wiley, New York (2004)
[19] Heinonen, J., Kipelainen, T., Martio, O.: Nonlinear Potential Theory of Degenerate Elliptic Equations. Courier Dover Publications, Mineola (2018)
[20] Henderson, D., Jacobson, S.H., Johnson, A.W.: The theory and practice of simulated annealing. In: Handbook of Metaheuristics, pp. 287-319. Springer (2003)
[21] Holland, J.H.: Holland. Genetic algorithms. Sci. Am. 267, 66-73 (1992)
[22] Kirkpatrick, S., Daniel Gelatt, C., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671-680 (1983)
[23] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 385-482 (2003)
[24] Lagarias, J.C., Reeds, J.A., Wright, M.H., Wright, P.E.: Convergence properties of the Nelder-Mead simplex method in low dimensions. SIAM J. Optim. 9, 112-147 (1998)
[25] Larson, J., Menickelly, M., Wild, S.M.: Derivative-free optimization methods. Acta Numer. 28, 287-404 (2019)
[26] McKinnon, K.I.M.: Convergence of the Nelder-Mead simplex method to a non-stationary point. SIAM J. Optim. 9, 148-158 (1999)
[27] Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge (1998)
[28] Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308-313 (1965)
[29] Oleınik, O.A.: Linear equations of second order with nonnegative characteristic form. Mat. Sb. (NS) 69, 111-140 (1966)
[30] Pérez, C., Rela, E.: Degenerate Poincaré-Sobolev inequalities. Trans. Am. Math. Soc. 372(9), 6087-6133 (2019)
[31] Poli, R., Kennedy, J., Blackwell, T.: Particle swarm optimization. Swarm Intell. 1, 33-57 (2007)
[32] Rastrigin, L.A.: Systems of Extremal Control. Nauka, Moscow (1974)
[33] Shi, Y., Eberhart, R.: A modified particle swarm optimizer. In: 1998 IEEE International Conference on Evolutionary Computation Proceedings, pp. 69-73 (1998)
[34] Stroock, D.W., Srinivasa Varadhan, S.R.: Multidimensional Diffusion Processes. Springer Science & Business Media, Berlin (1997)
[35] Totzeck, C.: Trends in consensus-based optimization. arXiv:2104.01383 (2021)

Adaptive State-Dependent Diffusion for Derivative-Free Optimization

Adaptive State-Dependent Diffusion for Derivative-Free Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价