Simulated Annealing
Friday, May 26th, 2006This semester, since I was working on a computer vision project, I downloaded a bunch of articles on shape recognition, tracking, color correction, and such. A lot of the algorithms in these papers depend on some optimization algorithm, and these optimization algorithms are assumed to be known to the reader. It seems that simulated annealing, a method of optimization based on the simulation of certain physical mechanisms, can be used as a simple equivalent replacement algorithm for the more esoteric ones.
Here’s how simulated annealing works, as per “The Annealing Algorithm” by Otten and van Ginneken: we are given an instance of the problem, a pair 
consisting of a set of feasible configurations (aka configuration space) 
, and a score (aka objective) function 
, and our aim is to find an optimum state 
, satisfying
There are several ways to conduct this search: blind random searching, in which random configurations are generated and evaluated until some stopping condition is reached; iterative refinement, in which random configurations are generated and evaluated, then tested against their neighbors; in this method, a new starting random configuration considered when all the current one’s neighbors have been tested, and is switched to only if its score is lower than the current low score. Then there are probabilistic hill climbing methods, which keep the testing of neighbors present in the iterative refinement algorithm, but use an acceptance function to determine whether to switch to a new random starting point; this acceptance function has a nonzero probability of allowing a switch to a starting configuration with a higher score. By visualizing the score vs. configuration surface, you can see why probabilistic hill climbing methods are appropriately named: while iterative refinement algorithms can only move down the surface, these methods allow moving up hills; the advantage of allowing this is that it makes the algorithm less sensitive to local minima.
Simulated annealing is a probabilistic hill climbing optimization method motivated by physical principles– I won’t go into the details, because they’re not too important: the method is straightforward enough by itself. To use this method, you need a single parameter
be such that 
is continuous and ![\text{supp } \hat{\varphi} \subseteq \left[-\frac{1}{2}, \frac{1}{2}\right]^2](/cz/latexrender/pictures/2b202ef84568befc9ade1f34ea3c5547.png "\text{supp } \hat{\varphi} \subseteq \left[-\frac{1}{2}, \frac{1}{2}\right]^2")
. Then 
is not a frame, but it is a Bessel sequence.
![\text{supp }\hat{v} \not\subseteq \left[-\frac{1}{2}, \frac{1}{2}\right]^2](/cz/latexrender/pictures/9bf4fc3e8bdc4a7e465a0b9588ab8301.png "\text{supp }\hat{v} \not\subseteq \left[-\frac{1}{2}, \frac{1}{2}\right]^2")
then 
, so the lower bound condition is violated. 
. Then consider ![g = \overline{\hat{\varphi}}\hat{v}|_{\left[-\frac{1}{2}, \frac{1}{2}\right]^2}](/cz/latexrender/pictures/36fd24d3ddb221ef754adb3819fdf666.png "g = \overline{\hat{\varphi}}\hat{v}|_{\left[-\frac{1}{2}, \frac{1}{2}\right]^2}")
; 
satisfies ![\|g\|_{\left[-\frac{1}{2}, \frac{1}{2}\right]^2} \leq \|\varphi\|_\infty \|v\|_{L^2(\R^2)}](/cz/latexrender/pictures/9579041ca4e3535631a1d64f2a757493.png "\|g\|_{\left[-\frac{1}{2}, \frac{1}{2}\right]^2} \leq \|\varphi\|_\infty \|v\|_{L^2(\R^2)}")
, so we can consider ![L^2(\left[-\frac{1}{2}, \frac{1}{2}\right]^2)](/cz/latexrender/pictures/7d48fd8ee4d64a134b49be09e7978b74.png "L^2(\left[-\frac{1}{2}, \frac{1}{2}\right]^2)")
. Then we have
.
. Per Juan, this is because the statement of the problem should be
and 
, then 
, so 
).
spans 
then there are 
such that
.
defined by 
is linear, so by the above result is bounded with some constant 
.
…
.
is again a linear function on a finite dimensional vector space, so it is bounded by some constant 
. We can take 
.
that is not a frame, because it is not a Bessel sequence (a sequence which defines a bounded operator 
): simply let 
.
be a smooth m-dimensional manifold, with 
, then 
where 
is the Lebesgue measure. Hopefully I’ll have all the machinery I need to examine this question after chapter 2.
, had measure zero, but couldn’t get a handle on that, since the set of zeros is some complex variety. Now, using Robert’s technique, it seems straightforward to show that the measure of any affine variety is zero.
centered at the origin satisfies the following property:
denotes Lebesgue measure and 
is a real function. That is, the volume of the intersection of 
matrix of integers, what is the probability that it is
and an integer 
of integers each less than 
? I don’t know.
: from an 