On an Efficient Distribution of Perturbations for Simulation Optimization using Simultaneous Perturbation Stochastic Approximation

摘要

Stochastic approximation as a method of simulation optimization is well-studied and numerous practical applications exist. One approach, simultaneous perturbation stochastic approximation (SPSA), has proven to be an efficient algorithm for such purposes. SPSA uses a centered difference approximation to the gradient based on two function evaluations regardless of the dimension of the problem. It accomplishes this task by randomizing the directions in which the differences are calculated in each dimension. Typically Bernoulli variables mapped to {-1, 1} are used in the randomization and this distribution is known to be asymptotically most efficient, but the question of best distribution remains open for small-sample approximations. As part of a general theory of small-sample stochastic approximation, the author has studied alternative distributions for the perturbations used to compute the SPSA estimate of the gradient. This paper presents results from that investigation, as well as some insights to parameter selection for the SPSA algorithm.