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 expec tation of a random variable. In such problems, only samples of the random v ariables are available for the optimization process. An iterative algorithm called the stochastic comparison (SC) algorithm is developed. The converge nce of the SC algorithm is established based on an examination of the quasi -stationary probabilities of a time-inhomogeneous Markov chain. We also pre sent some numerical experiments.