A Kiefer-Wolfowitz algorithm with randomized differences

A Kiefer-Wolfowitz or simultaneous perturbation algorithm that uses either one-sided or two-sided randomized differences and truncations at randomly varying bounds is given in this paper. At each iteration of the algorithm only two observations are required in contrast to 2l observations, where l is the dimension, in the classical algorithm. The algorithm given is shown to be convergent under only some mild conditions. The rate of convergence and asymptotic normality of the algorithm are also established.