Comparison of the SPSA and simulated annealing algorithms for the constrained optimization of discrete non-separable functions

This paper considers a version of the simultaneous perturbation stochastic approximation (SPSA) algorithm and a simulated annealing (SAN) algorithm for optimizing non-separable functions over discrete sets under given constraints. The primary motivation for the application of these discrete optimization algorithms is to solve a class of resource allocation problems wherein the goal is to distribute a finite number of discrete resources to finitely many users in such a way as to optimize a specified objective function. The basic algorithms and their application to the optimal resource allocation problem are discussed and simulation results are presented which compare their performance.