Stochastic Localization Methods for Convex Discrete Optimization via Simulation

We develop and analyze a set of new sequential simulation-optimization algorithms for large-scale multidimensional discrete optimization via simulation problems with a convexity structure. The “large-scale” notion refers to that the discrete decision variable has a large number of values from which to choose on each dimension of the decision variable. The proposed algorithms are targeted to identify a solution that is close to the optimal solution given any precision level with any given probability. To achieve this target, utilizing the convexity structure, our algorithm design does not need to scan all the choices of the decision variable, but instead sequentially draws a subset of choices of the decision variable and uses them to “localize” potentially near-optimal solutions to an adaptively shrinking region. To show the power of the proposed methods based on the localization idea, we first consider one-dimensional large-scale problems. We develop the shrinking uniform sampling algorithm, which is proved to achieve the target with an optimal expected simulation cost under an asymptotic criterion. For multidimensional problems, we combine the idea of localization with subgradient information and propose a framework to design stochastic cutting-plane methods, whose expected simulation costs have a low dependence on the scale and the dimension of the problems. In addition, utilizing the discrete nature of the problems, we propose a stochastic dimension-reduction algorithm, which does not require prior information about the Lipschitz constant of the objective function, and its simulation costs are upper bounded by a value that is independent of the Lipschitz constant. We implement the proposed algorithms on synthetic problems and queueing simulation-optimization problems and demonstrate better performances compared with benchmark methods especially for large-scale examples.