Stochastic comparison algorithm for discrete optimization with estimation of time-varying objective functions (Q1969465)

Many applications lead (from the mathematical point of view) to optimization problems in which 1) it is necessary to find the max (min) of a function over a discrete (rather large) set, 2) the ``objective'' function can be determined only through its unbiased statistical estimates. Great attention has been already paid (in the literature) to the above mentioned problems. In particular, stochastic solution algorithms were suggested and simultaneously investigated. To obtain convergence results the theory of Markov chains has usually been employed. The author of the paper tries to deal with a more complicated case. In particular, he considers the case of a time-varying objective function. According to this fact the suggested algorithms are only required to finish with a high probability at the optimum. Finally some examples illustrate the effectiveness of the proposed algorithm.