Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a s equence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable p roperty of solving a large class of global optimization problems using a nu mber of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly dist ributed in the improving feasible region. In this article, we derive a coup ling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly dist ributed point with a certain probability. This result is used to characteri ze the complexity of a PAS-implementation as a function of (a) the number o f iterations required by PAS to achieve a certain solution quality guarante e, and (b) the complexity of the sampling algorithm used. As an application , we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in p olynomial time.