  Contemporary global optimization algorithms are based on local measures of
utility, rather than a probability measure over location and value of the
optimum. They thus attempt to collect low function values, not to learn about
the optimum. The reason for the absence of probabilistic global optimizers is
that the corresponding inference problem is intractable in several ways. This
paper develops desiderata for probabilistic optimization algorithms, then
presents a concrete algorithm which addresses each of the computational
intractabilities with a sequence of approximations and explicitly adresses the
decision problem of maximizing information gain from each evaluation.
