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

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. Funding: The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST). D. A. Gomes was supported by KAUST [baseline funds and Grant KAUST OSR-CRG2021-4674]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2023.0340 .