Stochastic Optimization on Continuous Domains With Finite-Time Guarantees by Markov Chain Monte Carlo Methods

Author

Lecchini-Visintini, Andrea ; Lygeros, John ; Maciejowski, Jan M.

Author_Institution

Dept. of Eng., Univ. of Leicester, Leicester, UK

Volume

55

Issue

12

fYear

2010

Firstpage

2858

Lastpage

2863

Abstract

We introduce bounds on the finite-time performance of Markov chain Monte Carlo (MCMC) algorithms in solving global stochastic optimization problems defined over continuous domains. It is shown that MCMC algorithms with finite-time guarantees can be developed with a proper choice of the target distribution and by studying their convergence in total variation norm. This work is inspired by the concept of finite-time learning with known accuracy and confidence developed in statistical learning theory.

Keywords

Markov processes; Monte Carlo methods; convergence; learning (artificial intelligence); simulated annealing; Markov Chain Monte Carlo method; continuous domain; convergence; finite time guarantees; finite time learning; finite time performance; statistical learning theory; stochastic optimization; target distribution; total variation norm; Approximation algorithms; Convergence; Markov processes; Monte Carlo methods; Proposals; Simulated annealing; Markov chain Monte Carlo (MCMC);

fLanguage

English

Journal_Title

Automatic Control, IEEE Transactions on

Publisher

ieee

ISSN

0018-9286

Type

jour

DOI

10.1109/TAC.2010.2078170

Filename

5582214