Constrained optimization over discrete sets via SPSA with application to non-separable resource allocation

摘要

This paper presents a version of the simultaneous perturbation stochastic approximation (SPSA) algorithm for optimizing non-separable functions over discrete sets under given constraints. The primary motivation for discrete SPSA 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 algorithm and the application of the algorithm to the optimal resource allocation problem is discussed and simulation, results are presented which illustrate its performance.