AVERAGE PERFORMANCE OF PASSIVE ALGORITHMS FOR GLOBAL OPTIMIZATION

Passive algorithms for global optimization of a function choose observ ation points independently of past observed values. We study the avera ge performance of two common passive algorithms under the assumption o f Brownian motion prior. The first algorithm chooses equally spaced ob servation points, while the second algorithm chooses the observation p oints independently and uniformly distributed. The average convergence rate for both is O(n(-1/2)), with the second algorithm approximately 82% as efficient as the first. (C) 1995 Academic Press, Inc.