Paper Info
Title
Implementing pure adaptive search for global optimization using Markov chain sampling
Abstract
The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number 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 distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, 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 polynomial time.
Year
DOI
Venue
2001
10.1023/A:1011279301005
Journal of Global Optimization
Keywords
Field
DocType
Global optimization,Markov chain sampling,Coupling,Complexity
Mathematical optimization,Global optimization,Markov chain,Level set,Equivalence (measure theory),Feasible region,Sampling (statistics),Time complexity,Convex optimization,Mathematics
Journal
Volume
Issue
ISSN
20
1
1573-2916
Citations 
PageRank 
References 
6
0.81
10
Authors
3
Name
Order
Citations
PageRank
Daniel J. Reaume160.81
H. Edwin Romeijn276983.88
Robert L. Smith3664123.86