Stochastic Comparison Algorithm for Discrete Optimization with Estimation

In this paper we study a class of discrete optimization problems, where the objective function for a given configuration can be expressed as the expectation of a random variable. In such problems, only samples of the random variables are available for the optimization process. An iterative algorithm called the stochastic comparison (SC) algorithm is developed. The convergence of the SC algorithm is established based on an examination of the quasi-stationary probabilities of a time-inhomogeneous Markov chain. We also present some numerical experiments.