ORIGINAL PAPERS

Adaptive State-Dependent Diffusion for Derivative-Free Optimization

Expand
  • 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 date: 2023-02-09

  Revised date: 2023-09-14

  Accepted date: 2023-09-17

  Online published: 2024-01-09

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.

Cite this article

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 . DOI: 10.1007/s42967-023-00324-3

References

[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 l2 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)
Options
Outlines

/