2013/10/31 by Qi Wang, Wang, Qi
Computer Science · Decision Sciences · Mathematics · #Advanced Multi-Objective Optimization Algorithms #FOS: Mathematics #Modeling, Simulation, and Optimization #Optimization and Control (math.OC) #Simulation Techniques and Applications #math.OC
paper · pdf · doi:10.48550/arxiv.1311.0042
arxiv created 2013/10/31 · openalex publication_date 2013/10/31 · arxiv updated 2013/11/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.