A Dynamic Stochastic Approximation Method

This investigation has been inspired by a paper of V. Fabian [3], where inter alia the applicability of stochastic approximation methods for progressive improvement of production processes is discussed; his non-formal discussion includes the case where the optimum of the production process moves during the optimization process. In the present paper, the last case is treated in a formal way. A modified approximation scheme is suggested, which turns out to be an adequate tool, when the position of the optimum is a linear (or nearly linear) function of time. The domain of effectiveness of the unmodified approximation scheme is also investigated. In this context, the incorrectness of a theorem of T. Kitagawa is pointed out. The considerations are performed for the Robbins-Monro case in detail; they can all be repeated for the Kiefer-Wolfowitz case and for the multidimensional case, as indicated in Section 4. Among the properties of the method, only the mean convergence and the order of magnitude of E\ (xₙ - \θₙ)²\ are investigated; (here xₙ denotes the estimated and \θₙ the true position of the optimum at time n.) A lemma, due to K. L. Chung [1] is used repeatedly: LEMMA. Let bₙ, n = 1, 2, \⋯, be real numbers such that for n \ n₀, \{equation*}\{1}bn + 1 \ (1 - c/n^s)b_n + c'/n^t,\{equation*} where $0 < s < 1, c > 0, c' > 0, t$ real. Then \{equation*}\{2}\lim n \→ \∞ nt - sb_n \ c'/c.\{equation*} The lemma remains true, if the inequalities (1) and (2) are reversed and, simultaneously, lim n \→ \∞ is changed into lim \→ \∞. (In Chung's paper, a further assumption $t > s$ is made, but it is easily seen, that both versions of the lemma hold true also when t \ s; this fact is used in Section 3.) Throughout the paper, K₀, K₁, K₂, \⋯ denote positive constants, numbered in order of appearance.