Rates of Convergence for Sequential Monte Carlo Optimization Methods
Author:
- Harold J. KushnerHKHarold J. Kushner
- 1 January 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 16 (1) , 150-168
Abstract
Sequential Monte Carlo methods of the stochastic approximation (SA) type, with and without constraints, are discussed. The rates of convergence are derived, and the quantities upon which the rates depend, are discussed. Let $\{ {X_n } \}$ denote the SA sequence and define $U_n = (n + 1)^\beta X_n $ for a suitable $\beta > 0$. The $\{ {U_n } \}$ are interpolated into a natural continuous time process, and weak convergence theory is applied to develop the properties of the tails of the sequence. The technique has a number of advantages over past approaches—advantages which are discussed in the paper. It gives more insight (and is apparently more readily generalizable) than do other approaches—and suggests ways of improving the convergence. The particular “dynamical” nature of the approach allows one to say more about the “tail” process—and to do more “decision” (or “control”) analysis with it.
Keywords
This publication has 16 references indexed in Scilit:
- General convergence results for stochastic approximations via weak convergence theoryJournal of Mathematical Analysis and Applications, 1977
- Stochastic Approximation Algorithms of the Multiplier Type for the Sequential Monte Carlo Optimization of Stochastic SystemsSIAM Journal on Control and Optimization, 1976
- Counterexamples to general convergence of a commonly used recursive identification methodIEEE Transactions on Automatic Control, 1975
- Stochastic approximation of constrained systems with system and constraint noiseAutomatica, 1975
- Stochastic approximation type methods for constrained systems: Algorithms and numerical resultsIEEE Transactions on Automatic Control, 1974
- Stochastic Approximation Algorithms for Constrained Optimization ProblemsThe Annals of Statistics, 1974
- Penalty function methods for constrained stochastic approximationJournal of Mathematical Analysis and Applications, 1974
- Use of the augmented penalty function in mathematical programming problems, part 1Journal of Optimization Theory and Applications, 1971
- On Asymptotic Normality in Stochastic ApproximationThe Annals of Mathematical Statistics, 1968
- Asymptotic Distribution of Stochastic Approximation ProceduresThe Annals of Mathematical Statistics, 1958