Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization

We discuss desirable features that optimization algorithms should possess to exhibit good empirical performance when applied to solve simulation optimization problems possessing little known structure. Our framework emphasizes maintaining an appropriate balance between exploration, exploitation, and estimation. With the exception of estimation, our ideas are also applicable in (unstructured) deterministic optimization. Exploration refers to (globally) searching the entire feasible region for promising solutions, exploitation refers to the (local) search for improved solutions in promising subregions, and estimation refers to obtaining enhanced estimates of the objective function values at promising solutions and of the optimal solution. We also present two new random search methods that possess these desirable features, prove their almost-sure global convergence, and provide preliminary numerical results that suggest that the proposed framework is promising from a practical point of view.