Adaptive partitioned random search to global optimization

Abstract

This paper considers global optimization (maximization) problems. For a generic function, it is inherently difficult to find the global optimum within a finite number of function evaluations; it is more realistic to talk about maximizing the expectation of the largest function value that can be obtained for a given number of function evaluations. Based on decision theoretic argument, we propose that the search region of the objective function be partitioned into certain number of subregions. Using the sampled function values from each subregion, estimators are derived to determine how "promising" each subregion is. The most promising subregion is further partitioned. The proposed adaptive partitioned random search (APRS) is a tree search type of algorithms like branch-and-bound algorithms. The APRS, however, abandons the idea of finding the subregion where the global maximum is likely located in the first place. Instead it seeks the subregion where the largest improvement of the performance is most likely to be obtained if more function evaluations are taken. The APRS in general can provide a much better-than-average solution within a modest number of function evaluations. In fact, our various numerical experiments have shown that in comparison with the crude random search (CRS) in terms of number of function evaluations, the APRS can be at least hundreds of times more efficient. The simplicity and robustness of the APRS in terms of easy implementation and minimum assumptions are also demonstrated.