Implementing pure adaptive search for global optimization using Markov chain sampling (Q5942318)

A theoretical method known as the Pure Adaptive Search (PAS) has an attractive property: number of iterations to achieve the solution with an error not exceeding the predefined tolerance increases at most linearly with the dimension of the problem. However, the algorithmic implementation of this method is not obvious. The authors analyze the possibility to apply Markov samplers for approximate implementation of PAS. It is shown that the random ball walk is polynomial for solving a convex programming problem with probability at least \(1-\alpha \).