Billiard walk - A new sampling algorithm for control and optimization

B. T. Polyak, E. N. Gryazina

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

Hit-and-Run is known to be one of the best versions of Markov Chain Monte Carlo sampler. Nevertheless, in practice the number of iterations required to achieve uniformly distributed samples is rather high. We propose new random walk algorithm based on billiard trajectories and prove its asymptotic uniformity. Numerical experiments demonstrate much faster convergence to uniform distribution for Billiard Walk algorithm compared to Hit-and-Run. We discuss a class of global optimization problems that can be efficiently solved with Monte Carlo sampler.

Original languageEnglish
Title of host publication19th IFAC World Congress IFAC 2014, Proceedings
EditorsEdward Boje, Xiaohua Xia
PublisherIFAC Secretariat
Pages6123-6128
Number of pages6
ISBN (Electronic)9783902823625
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014 - Cape Town, South Africa
Duration: 24 Aug 201429 Aug 2014

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Volume19
ISSN (Print)1474-6670

Conference

Conference19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014
Country/TerritorySouth Africa
CityCape Town
Period24/08/1429/08/14

Keywords

  • Global optimization
  • Hit-and-Run
  • Linear systems
  • Randomized methods
  • Stabilization

Fingerprint

Dive into the research topics of 'Billiard walk - A new sampling algorithm for control and optimization'. Together they form a unique fingerprint.

Cite this