On the convergence of two sequential Monte Carlo methods for maximum a posteriori sequence estimation and stochastic global optimization Articles uri icon

publication date

  • January 2013

start page

  • 91

end page

  • 107

issue

  • 1

volume

  • 23

international standard serial number (ISSN)

  • 0960-3174

electronic international standard serial number (EISSN)

  • 1573-1375

abstract

  • This paper addresses the problem of maximum a posteriori (MAP) sequence estimation in general state-space models. We consider two algorithms based on the sequential Monte Carlo (SMC) methodology (also known as particle filtering). We prove that they produce approximations of the MAP estimator and that they converge almost surely. We also derive a lower bound for the number of particles that are needed to achieve a given approximation accuracy. In the last part of the paper, we investigate the application of particle filtering and MAP estimation to the global optimization of a class of (possibly non-convex and possibly non-differentiable) cost functions. In particular, we show how to convert the cost-minimization problem into one of MAP sequence estimation for a state-space model that is "matched" to the cost of interest. We provide examples that illustrate the application of the methodology as well as numerical results.

keywords

  • sequential monte carlo; map sequence estimation; convergence of particle filters; state space models; global optimization