Direction choice for accelerated convergence in hit-and-run sampling
成果类型：
Article
署名作者：
Kaufman, DE; Smith, RL
署名单位：
AT&T; University of Michigan System; University of Michigan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.1.84
发表日期：
1998
页码：
84-95
关键词：
摘要：
Hit-and-Run algorithms are Monte Carlo procedures for generating points that are asymptotically distributed according to general absolutely continuous target distributions G over open bounded regions S. Applications include nonredundant constraint identification, global optimization, and Monte Carlo integration. These algorithms are reversible random walks that commonly incorporate uniformly distributed step directions. We investigate nonuniform direction choice and show that, under regularity conditions on the region S and target distribution G, there exists a unique direction choice distribution, characterized by necessary and sufficient conditions depending on S and G, which optimizes the Doob bound on rate of convergence. We include computational results demonstrating greatly accelerated convergence for this optimizing direction choice as well as for more easily implemented adaptive heuristic rules.