A stochastic steepest-descent algorithm

A stochastic steepest-descent algorithm for function minimization under noisy observations is presented. Function evaluation is done by performing a number of random experiments on a suitable probability space. The number of experiments performed at a point generated by the algorithm reflects a balance between the conflicting requirements of accuracy and computational complexity. The algorithm uses an adaptive precision scheme to determine the number of random experiments at a point; this number tends to increase whenever a stationary point is approached and to decrease otherwise. Two rules are used to determine the number of random experiments at a point; one, in the inner loop of the algorithm, uses the magnitude of the observed gradient of the function to be minimized; and the other, in the outer-loop, uses a measure of accumulated errors in function evaluations at past points generated by the algorithm. Once a stochastic approximation of the function to be minimized is obtained at a point, the algorithm proceeds to generate the next point by using the steepest-descent deterministic methods of Armijo and Polak (Refs. 3, 4). Convergence of the algorithm to stationary points is demonstrated under suitable assumptions.