Discrete Backtracking Adaptive Search for Global Optimization
Birna P. Kristinsdottir, Zelda B. Zabinsky, Graham R. Wood · Kluwer Academic Publishers eBooks · 2005
This paper analyses a random search algorithm for global optimization that allows acceptance of non-improving points with a certain probability. The algorithm is called discrete backtracking adaptive search. We derive upper and lower bounds on the expected number of iterations for the random search algorithm to first sample the global optimum. The bounds are derived by modeling the algorithm using a series of absorbing Markov chains. Finally, upper and lower bounds for the expected number of iterations to find the global optimum are derived for specific forms of the algorithm.