Global Optimization: Partitioned Random Search and Optimal Index Policies

We consider a combination of state space partitioning and random search methods for solving deterministic global optimization problem. We assume that function computations are costly and finding global optimum is difficult. Therefore, we may decide to stop searching long before we found a solution close to the optimum. Final reward of the algorithm is defined as the best found function value minus total cost of computations. We construct index sampling policy that is asymptotically optimal on average when number of the search regions k is large. Sampling index for each search region is defined as the stopping value of sampling from that region only. Stopping value selection policy is an improvement over myopic and heuristic index rules that are used in partitioned random search and stochastic branch-andbound algorithms. 1 Introduction We consider a problem of global optimization of a function f(x) : A ! R where A ae R d (d 1). Finding the true global optimum x = arg max x2A ff(..