Pure adaptive search in global optimization (Q1184353)

The authors provide a theoretical analysis of pure adaptive search for general global optimization. The algorithm proceeds by generating a sequence of points uniformly distributed in a sequence of nested regions of the feasible space. At any iteration the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly better in value to the previous points in the sequence. It has been shown in a paper by \textit{N. R. Patel, R. L. Smith, Z. B. Zabinsky} and \textit{B. Zelda} [ibid. 43, No. 3, 317-328 (1989; Zbl 0671.90047)] that for convex programs the expected number of iterations required to achieve a given accuracy of the solution increases at most linearly in the dimension of the problem. In this paper, the authors extend this linear complexity result for non-convex or global optimization problems satisfying the Lipschitz condition.