  Discrete stochastic optimization considers the problem of minimizing (or
maximizing) loss functions defined on discrete sets, where only noisy
measurements of the loss functions are available. The discrete stochastic
optimization problem is widely applicable in practice, and many algorithms have
been considered to solve this kind of optimization problem. Motivated by the
efficient algorithm of simultaneous perturbation stochastic approximation
(SPSA) for continuous stochastic optimization problems, we introduce the middle
point discrete simultaneous perturbation stochastic approximation (DSPSA)
algorithm for the stochastic optimization of a loss function defined on a
p-dimensional grid of points in Euclidean space. We show that the sequence
generated by DSPSA converges to the optimal point under some conditions.
Consistent with other stochastic approximation methods, DSPSA formally
accommodates noisy measurements of the loss function. We also show the rate of
convergence analysis of DSPSA by solving an upper bound of the mean squared
error of the generated sequence. In order to compare the performance of DSPSA
with the other algorithms such as the stochastic ruler algorithm (SR) and the
stochastic comparison algorithm (SC), we set up a bridge between DSPSA and the
other two algorithms by comparing the probability in a big-O sense of not
achieving the optimal solution. We show the theoretical and numerical
comparison results of DSPSA, SR, and SC. In addition, we consider an
application of DSPSA towards developing optimal public health strategies for
containing the spread of influenza given limited societal resources.
