A Metropolis-Type Optimization Algorithm on the Infinite Tree

Let S(v) be a function defined on the vertices v of the infinite binary tree. One algorithm to seek large positive values of S is the Metropolis-type Markov chain (X _n ) defined by for each neighbor w of v , where b is a parameter (``1/temperature") which the user can choose. We introduce and motivate study of this algorithm under a probability model for the objective function S , in which S is a ``tree-indexed simple random walk," that is, the increments (e) = S(w)-S(v) along parent—child edges e = (v,w) are independent and P ( = 1) = p , P( = -1) = 1-p . This algorithm has a ``speed" r(p,b) = lim _n n ^-1 ES(X _n ) . We study the speed via a mixture of rigorous arguments, nonrigorous arguments, and Monte Carlo simulations, and compare with a deterministic greedy algorithm which permits rigorous analysis. Formalizing the nonrigorous arguments presents a challenging problem. Mathematically, the subject is in part analogous to recent work of Lyons et al. 19], 20] on the speed on random walk on Galton—Watson trees. A key feature of the model is the existence of a critical point p _crit below which the problem is infeasible; we study the behavior of algorithms as p p _crit. This provides a novel analogy between optimization algorithms and statistical physics. Received September 8, 1997; revised February 15, 1998.