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

• 成果类型: Article; Early Access
• 署名作者: Gomes, Alexandra A.; Gomes, Diogo A.
• 署名单位: King Abdullah University of Science & Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0340
• 发表日期: 2025
• 关键词: mead simplex-method; differential evolution; global optimization; Random search; CONVERGENCE

摘要

We introduce a derivative-free optimization algorithm that efficiently computes minima for various classes of one-dimensional functions, including nonconvex and nonsmooth functions. This algorithm numerically approximates the gradient flow of a relaxed functional, integrating strategies such as Monte Carlo methods, rejection sampling, and adaptive techniques. These strategies enhance performance in solving a diverse range of optimization problems while significantly reducing the number of required function evaluations compared with established methods. We present a proof of the convergence of the algorithm for locally convex functions and illustrate its numerical performance by comprehensive benchmarking with test functions, showcasing different properties and characteristics. The proposed algorithm offers a substantial potential for real-world models. It is particularly advantageous in situations requiring computationally intensive objective function evaluations, such as hyperparameter tuning in machine learning or line search in large-scale optimization problems involving the discretization of partial differential equations.