3 ms·
> It's fairly easy to prove that simulated annealing done "properly" will converge to a uniform distribution over all global minima. The "properly" here involve
by carlob 12y ago
> It's fairly easy to prove that simulated annealing done "properly" will converge to a uniform distribution over all global minima. The "properly" here involves a logarithmic cooling schedule and a little thought should convince you that this is in practice not going to help you any more than exhaustive search will.
Are you sure this is proven? What if ergodicity is broken?
- ska 12y agoToo late to edit the parent, but you are right to call me out on this, thanks!. Clearly without some ergodicity constraint you cannot have uniform distribution. I was sloppy with terminology, sorry. The original approach to this require weak and strong ergodicity conditions on an inhomogeneous Markov chain (but not stationarity of the chain, i.e. you don't have to run it forever). This was worked out in the mid 80s by Gidas and Mitra if I recall correctly, and several interesting updates since then. There are other probabilistic arguments made as well, after that. I can dig out references if anyone asks.
- carlob 12y agoThe problem then is that proving ergodicity is extremely hard for anything that is not a Markov chain to begin with. IIRC ergodicity of hard spheres is not yet proved in full generality (n spheres, d dimensions), and that's basically the simplest physical system there is!