A Parallel Depth-first Search Algorithm for Global Optimization Using Interval Analysis: The Single Variable Case

摘要

Finding the global minimum of an arbitrary differentiable function over an rt-dimensional rectangle is an important problem in computational science, with applications in many disciplines. We have developed a depth-first search method to reliably obtain the global minimum of an arbitrary continuously differentiable function in the one-dimensional case. Our algorithm reliably computes the global minimum for standard test functions in the literature, and requires much less computational effort than previously used breadth-first search methods. A parallel implementation of the algorithm demonstrates the expected speed-up as the number of processors is increased. Our method can be extended to the multidimensional case, which will be reported in a future publication.