Gradient-based Simulation-Optimization Algorithms via Approximations for Complex Stochastic Systems

We propose gradient-based simulation-optimization algorithms to optimize systems that have complicated stochastic structure. The presence of complicated stochastic structure, such as the involvement of infinite-dimensional continuous-time stochastic processes, may cause the exact simulation of the system to be costly or even impossible. On the other hand, for a complicated system, one can often construct a sequence of approximations at different resolutions, where the sequence has finer and finer approximation resolution but higher and higher cost to simulate. With the goal of optimizing the complicated system, we propose algorithms that strategically use the approximations with increasing resolution and higher simulation cost to construct stochastic gradients and perform gradient search in the decision space. To accommodate scenarios where approximations cause discontinuities and lead path-wise gradient estimators to have an uncontrollable bias, the construction of stochastic gradients for the proposed algorithms is done through finite difference. As a theory support, we prove algorithm convergence, convergence rate, central limit theorem, and optimality of algorithm design under the assumption that the objective function for the complicated system is strongly convex, while no such assumptions are imposed on the approximations of the complicated system. We then present a multilevel version of the proposed algorithms to further improve convergence rates, when in addition the sequence of approximations can be naturally coupled