Asymptotic behavior of constrained stochastic approximations via the theory of large deviations

Summary Let G be a bounded convex set, and _G the projection onto G, and a bounded random process. Projected algorithms of the types , where 0<a _n0, a _n =) occur frequently in applications (among other places) in control and communications theory. The asymptotic convergence properties of {X _n } as 0, n, have been well analyzed in the literature. Here, we use large deviations methods to get a more thorough understanding of the global behavior. Let be a stable point of the algorithm in the sense that X _n in distribution as 0, n. For the unconstrained case, rate of convergence results involve showing asymptotic normality of , and use linearizations about . In the constrained case is often on G, and such methods are inapplicable. But the large deviations method yields an alternative which is often more useful in the applications. The action functionals are derived and their properties (lower semicontinuity, etc.) are obtained. The statistics (mean value, etc.) of the escape times from a neighborhood of are obtained, and the global behavior on the infinite interval is described.Research has been supported in part by the US Army Research Office under Contract #DAAG 29-84-K-0082, and in part by the Office of Naval Research under Contract #N00014-83-K0542Research has been supported in part by the National Science Foundation Grant #ECS 82-11476, and the Air Force Office of Scientific Research under Contract #AF-AFOSR 81-0116