Simulated annealing for convex optimization

We apply the method known as simulated annealing to the following problem in convex optimization: Minimize a linear function over an arbitrary convex set, where the convex set is specified only by a membership oracle. Using distributions from the Boltzmann–Gibbs family leads to an algorithm that needs only O ^*(√n) phases for instances in ℝ ⁿ . This gives an optimization algorithm that makes O ^*(n ^4.5) calls to the membership oracle, in the worst case, compared to the previous best guarantee of O ^*(n ⁵).