Optimization via the strategic law of large numbers

Abstract

This paper proposes a framework for the global optimization of a possibly multimodal continuous function in a bounded rectangular domain. We first show that global optimization is equivalent to an optimal (sampling) strategy formation in a two-armed decision model with known distributions, based on the strategic law of large numbers we establish. There are many optimal strategies in general. We show that a concrete strategy using the sign of the partial gradient of the unique solution to a parabolic partial differential equation (PDE) is asymptotically optimal. Motivated by these results, we propose a class of Strategic Monte Carlo Optimization (SMCO) algorithms, which uses a simple strategy that makes coordinate-wise two-armed decisions based on the signs of the partial gradient (or practically the first difference) of the objective function, without the need of solving PDEs. Under some sufficient conditions, we establish that our SMCO algorithm converges to a local optimizer from a single starting point, and to a global optimizer under a growing set of starting points. Extensive numerical studies demonstrate the suitability of our SMCO algorithms for global optimization well beyond the theoretical guarantees established herein. For a wide range of deterministic and random test functions with challenging landscapes (multimodal, nondifferentiable, discontinuous), our SMCO algorithms perform robustly well, even in high-dimensional ( d = 200 ∼ 1 , 000 ) settings. In fact, our algorithms outperform many state-of-the-art global optimizers, as well as local algorithms (with the same set of starting points as ours).