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

D.W. Hutchison (USA)


simulation optimization, SPSA, stochasticapproximation, iterative algorithms, stochastic gradient.


Stochastic approximation as a method of simulation opti mization is well-studied and numerous practical applica tions exist. One approach, simultaneous perturbation sto chastic approximation (SPSA), has proven to be an effi cient 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 ques tion 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.

Important Links:

Go Back