Direction choice in random walk algorithms with application to global optimization.
David E. Kaufman · Deep Blue (University of Michigan) · 1993
Our problem is to randomly sample points from any of a broad class of continuous probability distributions (called target distributions) over an arbitrary open bounded region S in n-dimensional Euclidean space. Possible applications include nonredundant constraint identification, global optimization, and Monte Carlo integration. In the absence of efficient general-purpose methods for exact sampling, we study approximate but asymptotically exact sampling from the target distribution by means of random walk algorithms, which proceed iteratively by taking random step sizes in independent and identically distributed random directions, generating a sequence of iterates lying in S. It is known that if the step size rule preserves reversibility of the underlying Markov chain, the distributions of iterates converge in total variation to the target distribution for virtually any distribution of directions. Our task is to choose a direction distribution which accelerates convergence to the target distribution. We derive a lower bound on the convergence rate as a surrogate for average performance, prove existence and uniqueness of the direction distribution optimizing the bound, and characterize it by necessary and sufficient conditions. Because it may also be difficult to optimally generate directions, we present cases where optimal direction samples are simple transformations of samples from the target distribution, heuristically motivating an adaptive direction choice rule which introduces dependence of directions on prior history. We present empirical results indicating that optimal and adaptive choice perform much more robustly than uninformed direction choice with respect to variations in the geometry of S. As previous convergence theorems do not apply to this non-Markovian case, we provide some sufficient conditions for convergence of general adaptive rules. We take up the Hide-and-Seek simulated annealing algorithm of Romeijn and Smith for continuous global optimization; it samples approximately from Boltzmann distributions that concentrate about the global optimum as the algorithm progresses. We extend their analysis of quadratic problems to derive the optimal direction distribution for the Boltzmann sampling problems, motivating two new Hide-and-Seek direction rules which introduce gradient information into Hide-and-Seek. We demonstrate substantially improved optimization performance on a set of unconstrained optimization testproblems.