Parallel global optimization using interval analysis
Asai Asaithambi, Adam Baldwin · 2011
Finding the global minimum for an arbitrary differentiable function over an n-dimensional rectangle is an important problem in computational science, with applications in many disciplines. Ongoing research in this area has led to many exhaustive search methods that require significant computational effort. Our current research is aimed at identifying opportunities for parallelizing the search wherever possible so that the computing time is reduced, and the global minimum is obtained reliably for a wide variety of objective functions commonly explored in the literature. Our approach is to use a branch of applied mathematics known as Interval Analysis, which is a commonly used tool in obtaining lower and upper bounds for machine computations for the purpose of automatic error bounding. This ensures the reliability of the solutions obtained. We present a depth-first parallel branch and bound algorithm with acceleration methods that provides a significant reduction in run time compared to a popular breadth-first search algorithm. Our algorithm reliably obtains global minima for numerous test functions reported in the literature, with the highest speedup achieved for highly multimodal functions. Our algorithm possesses desirable properties of reliability, robustness, scalability, and load balancing, all of which will be demonstrated.