Search

The main goal of this chapter is to obtain the result at the end of section 6.3 which is part of the basis for the initialization of annealing as described in section 8.1. On the way to this result we formally define some density functions that are going to be used in chapter 7. After all this effort to obtain theorem 6.14 it is only a small step to the special case of the central limit theorem of section 6.4. This chapter is therefore the background of much that is in chapter 7 and the proof of theorem 8.2. The presentation there is such that it can be read without going through the details of this chapter. These results are achieved by using the characteristic function of a random variable. In section 6.1 this function is defined and some of its more important properties are derived.

1 The Annealing Algorithm: A Preview.- 1.1 Combinatorial optimization.- 1.2 Moves and local minima.- 1.3 Hill climbing.- 1.4 Simulated annealing.- 1.5 Applications.- 1.6 Mathematical model.- 1.7 Discussion.- 2 Preliminaries from Matrix Theory.- 2.1 Matrices. Notation and basic properties.- 2.2 Pseudo-diagonal normal forms.- 2.3 Norms and limits of matrices.- 2.4 Quadratic forms.- 2.5 Discussion.- 3 Chains.- 3.1 Terminology.- 3.2 Linear arrangement, an example.- 3.3 The chain limit theorem.- 3.4 Reversible chains.- 3.5 Discussion.- 4 Chain Statistics.- 4.1 Density Functions.- 4.2 Expected values.- 4.3 Sampling.- 4.4 Maximum likelyhood densities.- 4.5 Aggregate functions.- 4.6 Discussion.- 5 Annealing Chains.- 5.1 Towards low scores.- 5.2 Maximal accessibility.- 5.3 The acceptance function.- 5.4 Properties of annealing chains.- 5.5 Discussion.- 6 Samples from Normal Distributions.- 6.1 Characteristic functions.- 6.2 Quadratic forms and characteristic functions.- 6.3 Sampling distributions.- 6.4 Asymptotic properties of sampling distributions.- 6.5 Discussion.- 7 Score Densities.- 7.1 The density of states.- 7.2 Weak control.- 7.3 Strong control.- 7.4 Three parameter aggregates.- 7.5 Discussion.- 8 The Control Parameter.- 8.1 Initialization.- 8.2 Decrements in the control parameter.- 8.3 A stop criterion.- 8.4 Proper convergence.- 8.5 Discussion.- 9 Finite-Time Behavior of the Annealing Algorithm.- 9.1 Rate of convergence of chains.- 9.2 Minimum number of iterations.- 9.3 Finite-time optimal schedules.- 9.4 Discussion.- 10 The Structure of the State Space.- 10.1 Chain convergence.- 10.2 The topography of the state space.- 10.3 The set of moves.- 10.4 Global convergence.- 10.5 Discussion.- 11 Implementation Aspects.- 11.1 An implementation.- 11.2 The selection function.- 11.3 Other speed-up methods.- References.