|
Article Excerpt
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.sup.*]([square root of n]) phases for instances in [[??].sup.n]. This gives an optimization algorithm that makes [O.sup.*]([n.sup.4.5]) calls to the membership oracle, in the worst case, compared to the previous best guarantee of [O.sup.*]([n.sup.5]).
The benefits of using annealing here are surprising because such problems have no local minima that are not also global minima. Hence, we conclude that one of the advantages of simulated annealing, in addition to avoiding poor local minima, is that in these problems it converges faster to the minima that it finds. We also give a proof that under certain general conditions, the Boltzmann-Gibbs distributions are optimal for annealing on these convex problems.
Key words: convex optimization; simulated annealing; linear programming; MCMC MSC2000 subject classification: Primary: 90C05, 65C40; secondary: 90C25, 68W20 OR/MS subject classification: Primary: programming, linear algorithms; secondary: probability, random walk
1. Introduction. Simulated annealing, proposed by Kirkpatrick et al. [12], is a randomized search method for optimization. It tries to improve a solution by walking randomly in the space of possible solutions and gradually adjusting a parameter called "temperature." At high temperature, the random walk is almost unbiased, and it converges to essentially the uniform distribution over the whole space of solutions; as the temperature drops, each step of the random walk is more likely to move toward solutions with a better objective value, and the distribution is more and more biased toward the optimal solutions. The sequence of temperatures and lengths of time for which they are maintained is called the annealing schedule in analogy with statistical mechanics.
Although notoriously difficult to analyze, the usual justification for its empirical success (Press et al. [19]) is that "it avoids getting stuck in local optima." In this paper, we analyze it on problems where all the local optima are also global optima. Our results suggest that annealing has further advantages besides avoiding local optima. In particular, it also speeds up convergence to the optimum.
An important problem in this class is minimizing a linear function over a convex set. In the most general version, the convex set is presented only by a membership oracle (Grotchel et al. [7]). In [section]4, we show that simulated annealing, which can be viewed as an interior-point algorithm, takes only [O.sup.*] ([square root of n]) phases and [O.sup.*]([n.sup.4.5]) oracle queries to solve this problem. It is faster than the current best algorithm by a factor of [square root of n]. (The [O.sup.*](*) notation hides polylogarithmic factors in the parameters of the problem, i.e., [log.sup.k](n[R.sup.2]/(r[epsilon][delta])), where k is a constant; n is the dimensionality of the problem; [epsilon] is the distance from optimality; R/r is the ratio of containing and contained balls for the convex set; and the algorithm succeeds with probability 1 - [delta].) These facts illustrate (and provide a rigorous guarantee for) the advantage of simulated annealing even for problems with no bad local minima.
Simulated annealing is a special case of a stochastic search method that starts with one distribution (e.g., uniform over a given convex body) and gradually changes it to another target distribution (e.g., one that is concentrated near the optimum). The intermediate distributions satisfy the following two properties:
(i) Any two consecutive distributions must not be too different; one way to formalize this idea is to require that their total variation distance (see [section]3) is bounded away from 1.
(ii) All of the distributions along the way must be efficiently sampleable. The most general class of distributions for which we currently have efficient sampling algorithms is the class of logconcave distributions. In simulated annealing, the intermediate distributions are all from the exponential family (density at x is proportional to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some vector c) restricted to some domain. The random walk algorithm of Bertsimas and Vempala [2], for example, maintains a uniform distribution over a convex body. In each phase, it restricts the current convex body by a half space. This choice requires [O.sup.*](n) phases in the worst case.
From this perspective, it is natural to ask what choice of intermediate distributions would be optimal for convex problems. In [section]5, we show that in the worst case, the exponential family used in simulated annealing is in fact the best possible. We give an example where any method satisfying the above two properties needs [OMEGA]([square root of n]) phases. (1) Thus, in this sense, simulated annealing is an optimal stochastic search method. Moreover, we have shown yet another optimality property of the Boltzmann distributions (a different, well-known property is that of maximum entropy).
Finally, in [section]6, we suggest how the algorithm might be extended to the problem of minimizing a convex function over a convex set, where again the set is specified by a membership oracle. While our results show that the number of phases will be [O.sup.*]([square root of n]) for any convex function, further analysis of rapidly mixing walks for logconcave functions is required to achieve the [O.sup.*]([n.sup.4.5]) membership queries guarantee. Our approach here shows that one can move between any two logconcave densities in [O.sup.*] ([square root of n]) steps where each step moves between logconcave densities whose total variation distance is bounded away from 1.
1.1. Related work. Our approach is an improvement on the algorithm of Bertsimas and Vempala [2], which introduced the analysis of an efficient stochastic search method for convex optimization but required [O.sup.*](n) phases. Their method, involving a sequence of uniform distributions over sets with smaller objective function values c x x, is illustrated in Figure 1. Lovasz and Vempala [16] used a reverse annealing technique for estimating volume where they slowly increased the temperature. Our analysis is similar to theirs, and we will use some of the tools developed there.
[FIGURE 1 OMITTED]
Stochastic search methods have been analyzed for special cases of global optimization (see Zabinsky [24], Zabinsky et al. [25]). It is known that an exponentially long annealing schedule can guarantee convergence to the global optimum (even for non convex problems) (Hajek [8]). Simulated annealing has also been shown to be efficient for finding planted bisections in a random graph (Jerrum and Sorkin [9]) and for minimizing one-dimensional fractal functions (Sorkin [21]). Although originally proposed for discrete optimization problems, simulated annealing has been widely used for continuous optimization. The book by Spall [22] provides an introduction to both the theoretical and practical aspects of annealing.
2. Algorithm and guarantees. We apply annealing to the following linear minimization problem: for a unit vector c [member of] [[??].sup.n] and a convex set K [subset] [[??].sup.n],
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]
We assume only that we are given a membership oracle that identifies whether or not a point is in the set K as well as a starting point in it. As is standard (Grotchel et al. [7]), we need an upper bound R on the radius of a ball that contains K and a Iower bound r on the radius...
|
