A Derivative-Free Algorithm for Minimization in One Dimension: Relaxation, Monte Carlo, and Sampling

References

• [1] Akimoto Y, Nagata Y, Ono I, Kobayashi S (2010) Bidirectional relation between CMA evolution strategies and natural evolution strategies. Schaefer R, Cotta C, Kołodziej J, Rudolph G, eds. Parallel Problem Solving Nature, PPSN XI, Lecture Notes in Computer Science, vol. 6238 (Springer, Berlin, Heidelberg), 154–163.Google Scholar
• [2] Amari SI, Douglas SC (1998) Why natural gradient? Proc. 1998 IEEE Internat. Conf. Acoustics Speech Signal Processing, ICASSP98 (Cat. No. 98CH36181), vol. 2 (IEEE, Piscataway, NJ), 1213–1216.Google Scholar
• [3] Barricelli NA (1957) Symbiogenetic evolution processes realized by artificial methods. Methodos 9(35–36):601–610.Google Scholar
• [4] Bergstra J, Bengio Y (2012) Random search for hyper-parameter optimization. J. Machine Learn. Res. 13(10):281–305.Google Scholar
• [5] Berny A (2000) Selection and reinforcement learning for combinatorial optimization. Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP, eds. Parallel Problem Solving Nature, PPSN VI, Lecture Notes in Computer Science, vol. 1917 (Springer, Berlin, Heidelberg), 601–610.Google Scholar
• [6] Beyer HG, Schwefel HP (2002) Evolution strategies—A comprehensive introduction. Natural Comput. 1(1):3–52.Crossref, Google Scholar
• [7] Bosman PA, Thierens D (2000) Expanding from discrete to continuous estimation of distribution algorithms. Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP, eds. Parallel Problem Solving Nature, PPSN VI, Lecture Notes in Computer Science, vol. 1917 (Springer, Berlin, Heidelberg), 767–776.Google Scholar
• [8] Burden RL, Fairies JD (2011) Numerical Analysis (Cengage Learning, Boston).Google Scholar
• [9] Byrd RH, Schnabel RB, Shultz GA (1987) A trust region algorithm for nonlinearly constrained optimization. SIAM J. Numer. Anal. 24(5):1152–1170.Crossref, Google Scholar
• [10] Chaudhari P, Oberman A, Osher S, Soatto S, Carlier G (2018) Deep relaxation: Partial differential equations for optimizing deep neural networks. Res. Math. Sci. 5(3):1–30.Crossref, Google Scholar
• [11] Conn AR, Scheinberg K, Vicente LN (2009) Introduction to Derivative-Free Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [12] Das S, Mullick SS, Suganthan P (2016) Recent advances in differential evolution—An updated survey. Swarm Evolutionary Comput. 27:1–30.Crossref, Google Scholar
• [13] Del Ser J, Osaba E, Molina D, Yang XS, Salcedo-Sanz S, Camacho D, Das S, Suganthan PN, Coello Coello CA, Herrera F (2019) Bio-inspired computation: Where we stand and what’s next. Swarm Evolutionary Comput. 48:220–250.Crossref, Google Scholar
• [14] Diouane Y, Gratton S, Vicente LN (2015a) Globally convergent evolution strategies. Math. Programming 152(1):467–490.Crossref, Google Scholar
• [15] Diouane Y, Gratton S, Vicente LN (2015b) Globally convergent evolution strategies for constrained optimization. Comput. Optim. Appl. 62(2):323–346.Crossref, Google Scholar
• [16] Dolan ED, Lewis RM, Torczon V (2003) On the local convergence of pattern search. SIAM J. Optim. 14(2):567–583.Crossref, Google Scholar
• [17] Duchi JC, Jordan MI, Wainwright MJ, Wibisono A (2015) Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Trans. Inform. Theory 61(5):2788–2806.Crossref, Google Scholar
• [18] Garnett R (2022) Bayesian Optimization (Cambridge University Press, Cambridge, UK).Google Scholar
• [19] Ghadimi S, Lan G (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4):2341–2368.Crossref, Google Scholar
• [20] Ghosh S, Das S, Vasilakos AV, Suresh K (2012) On convergence of differential evolution over a class of continuous functions with unique global optimum. IEEE Trans. Systems Man Cybernetics Part B Cybernetics 42(1):107–124.Crossref, Google Scholar
• [21] Glasmachers T, Schaul T, Yi S, Wierstra D, Schmidhuber J (2010) Exponential natural evolution strategies. GECCO ‘10: Proc. 12th Annual Conf. Genetic Evolutionary Comput. (Association for Computing Machinery, New York), 393–400.Google Scholar
• [22] Glasserman P (2004) Monte Carlo Methods in Financial Engineering, Stochastic Modelling and Applied Probability, vol. 53 (Springer-Verlag, New York).Google Scholar
• [23] Goldberg DE (1989) Genetic Algorithm in Search Optimization and Machine Learning (Addison-Wesley Longman Publishing Co., Inc., Boston).Google Scholar
• [24] Hansen N (2006) The CMA evolution strategy: A comparing review. Lozano JA, Larrañaga P, Inza I, Bengoetxea E, eds. Towards a New Evolutionary Computation, Studies in Fuzziness and Soft Computing, vol. 192 (Springer, Berlin, Heidelberg), 75–102.Crossref, Google Scholar
• [25] Hansen N, Ostermeier A (1996) Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. Proc. IEEE Internat. Conf. Evolutionary Comput. (IEEE, Piscataway, NJ), 312–317.Google Scholar
• [26] Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evolutionary Comput. 9(2):159–195.Crossref, Google Scholar
• [27] Holland JH (1975) Adaptation in Natural and Artificial Systems (University of Michigan, Ann Arbor, MI).Google Scholar
• [28] Hooke R, Jeeves TA (1961) “Direct search” solution of numerical and statistical problems. J. ACM 8(2):212–229.Crossref, Google Scholar
• [29] Huyer W, Neumaier A (1999) Global optimization by multilevel coordinate search. J. Global Optim. 14(4):331–355.Crossref, Google Scholar
• [30] Kennedy J, Eberhart R (1995) Particle swarm optimization. Proc. ICNN’95 Internat. Conf. Neural Networks, vol. 4 (IEEE, Piscataway, NJ), 1942–1948.Google Scholar
• [31] Khachaturyan A, Semenovskaya S, Vainstein B (1979) Statistical-thermodynamic approach to determination of structure amplitude phases. Soviet Phys. Crystallography 24(5):519–524.Google Scholar
• [32] Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680.Crossref, Google Scholar
• [33] Lagarias JC, Reeds JA, Wright MH, Wright PE (1998) Convergence properties of the nelder-mead simplex method in low dimensions. SIAM J. Optim. 9(1):112–147.Google Scholar
• [34] Larrañaga P, Lozano JA, eds. (2001) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, vol. 2 (Springer Science & Business Media, New York).Google Scholar
• [35] Larson J, Menickelly M, Wild SM (2019) Derivative-free optimization methods. Acta Numer. 28:287–404.Crossref, Google Scholar
• [36] Locatelli M, Schoen F (2013) Global Optimization: Theory, Algorithms, and Applications (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [37] Locatelli M, Schoen F (2021) (Global) optimization: Historical notes and recent developments. EURO J. Comput. Optim. 9:100012.Crossref, Google Scholar
• [38] Locatelli M, Vasile M (2015) (Non) convergence results for the differential evolution method. Optim. Lett. 9(3):413–425.Crossref, Google Scholar
• [39] Lu J, Tadmor E, Zenginoğlu A (2024) Swarm-based gradient descent method for non-convex optimization. Comm. Amer. Mathematical Soc. 4:787–822.Google Scholar
• [40] Luus R, Jaakola THI (1973) Optimization by direct search and systematic reduction of the size of search region. AIChE J. 19(4):760–766.Crossref, Google Scholar
• [41] Ma X, Li X, Zhang Q, Tang K, Liang Z, Xie W, Zhu Z (2019) A survey on cooperative co-evolutionary algorithms. IEEE Trans. Evolutionary Comput. 23(3):421–441.Crossref, Google Scholar
• [42] Mansueto P, Schoen F (2021) Memetic differential evolution methods for clustering problems. Pattern Recognition 114:107849.Crossref, Google Scholar
• [43] Matyas J (1965) Random optimization. Automation Remote Control 26(2):246–253.Google Scholar
• [44] McKinnon KI (1998) Convergence of the Nelder–Mead simplex method to a nonstationary point. SIAM J. Optim. 9(1):148–158.Crossref, Google Scholar
• [45] Mockus J (1975) On Bayesian methods of optimization. Towards Global Optimization (North-Holland Publishing Company, Amsterdam), 166–181.Google Scholar
• [46] Mockus J, Tiesis V, Zilinskas A (1978) The application of Bayesian methods for seeking the extremum. Dixon LCW, Szegö GP, eds. Towards Global Optimization, vol. 2 (North-Holland Publishing Company, Amsterdam), 117–129.Google Scholar
• [47] Moré JJ, Sorensen DC (1983) Computing a trust region step. SIAM J. Sci. Statist. Comput. 4(3):553–572.Crossref, Google Scholar
• [48] Nelder JA, Mead R (1965) A simplex method for function minimization. Comput. J. 7(4):308–313.Crossref, Google Scholar
• [49] Nesterov Y, Spokoiny V (2017) Random gradient-free minimization of convex functions. Foundations Comput. Math. 17(2):527–566.Crossref, Google Scholar
• [50] Osher S, Heaton H, Wu Fung S (2023) A Hamilton-Jacobi-based proximal operator. Proc. Natl. Acad. Sci. 120(14):e2220469120.Google Scholar
• [51] Pelikan M, Goldberg DE, Lobo FG (2002) A survey of optimization by building and using probabilistic models. Comput. Optim. Appl. 21(1):5–20.Crossref, Google Scholar
• [52] Pincus M (1970) Letter to the editor—A Monte Carlo method for the approximate solution of certain types of constrained optimization problems. Oper. Res. 18(6):1225–1228.Link, Google Scholar
• [53] Powell MJD (1973) On search directions for minimization algorithms. Math. Programming 4:193–201.Crossref, Google Scholar
• [54] Price K, Storn RM, Lampinen JA (2006) Differential Evolution: A Practical Approach to Global Optimization (Springer-Verlag, Berlin, Heidelberg).Google Scholar
• [55] Rastrigin L (1963) The convergence of the random search method in the extremal control of a many parameter system. Automation Remote Control 24:1337–1342.Google Scholar
• [56] Rechenberg I (1973) Evolutionsstrategie. Optimierung Technischer Systeme Nach Prinzipien Derbiologischen Evolution (Friedrich Fromann Verlag, Stuttgart, Germany). [In German.]Google Scholar
• [57] Rios LM, Sahinidis NV (2013) Derivative-free optimization: A review of algorithms and comparison of software implementations. J. Glob. Optim. 56(3):1247–1293.Crossref, Google Scholar
• [58] Rubinstein RY, Kroese DP (2004) The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, vol. 133 (Springer Science & Business Media, New York).Crossref, Google Scholar
• [59] Schoen F, Tigli L (2021) Efficient large scale global optimization through clustering-based population methods. Comput. Oper. Res. 127:105165.Crossref, Google Scholar
• [60] Schwefel HP (1977) Evolutionsstrategien für die numerische optimierung. Numerische Optimierung Von Computer-Modellen Mittels Der Evolutionsstrategie, Interdisciplinary Systems Research/Interdisziplinäre Systemforschung (Birkhäuser, Basel, Switzerland), 123–176.Crossref, Google Scholar
• [61] Shi Y, Eberhart R (1998) A modified particle swarm optimizer. 1998 IEEE Internat. Conf. Evolutionary Comput. Proc. IEEE World Congress Comput. Intelligence (Cat. No. 98TH8360), (IEEE, Piscataway, NJ), 69–73.Google Scholar
• [62] Shultz GA, Schnabel RB, Byrd RH (1985) A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties. SIAM J. Numer. Anal. 22(1):47–67.Crossref, Google Scholar
• [63] Storn R, Price K (1997) Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4):341–359.Crossref, Google Scholar
• [64] Sun Y, Wierstra D, Schaul T, Schmidhuber J (2009) Efficient natural evolution strategies. GECCO ‘09: Proc. 11th Annual Conf. Genetic Evolutionary Comput. (Association for Computing Machinery, New York), 539–546.Google Scholar
• [65] Torczon V (1997) On the convergence of pattern search algorithms. SIAM J. Optim. 7(1):1–25.Crossref, Google Scholar
• [66] Vardhan H, Stich SU (2022) Tackling benign nonconvexity with smoothing and stochastic gradients. Preprint, submitted February 18, https://arxiv.org/abs/2202.09052.Google Scholar
• [67] Wierstra D, Schaul T, Glasmachers T, Sun Y, Peters J, Schmidhuber J (2014) Natural evolution strategies. J. Machine Learn. Res. 15(1):949–980.Google Scholar
• [68] Yang L, Shami A (2020) On hyperparameter optimization of machine learning algorithms: Theory and practice. Neurocomputing 415:295–316.Crossref, Google Scholar