Partitioned Random Search to Optimization

This paper considers the global optimization (maximization) problem. It emphasizes that for a generic function, it is inherently difficult to find the global maximum within a finite number of function evaluations. Therefore, it is more realistic to talk about maximizing the expectation of the largest function value that can possibly be obtained for a given number of function evaluations. In this spirit, we propose that the search region of the objective function be partitioned into certain number of subregions. Based on the sampled function values from each subregion, estimators are derived to determine how "promising" each subregion is. The most promising subregion is to be sampled next. Unlike many heuristic algorithms, the partitioned random search is mathematically well defined and the optimal solution has been found requiring few assumptions on an objective function. Our numerical results are also rather encouraging.