Search

In chapter 5 we derived that the probability that an annealing chain has s as its current state will go asymptotically to δ(s, t), the corresponding value of the equilibrium density. Nothing was said however about how fast these probabilities will approach the equilibrium density. Yet it is necessary to know a priori when the actual density is close enough to the equilibrium density to change the value of the control parameter and to start with another chain. In this chapter we want to address that problem.

In this chapter we review the matrix theory used in this book. The purpose of the first section is to introduce the notation and to call to memory results derived in any core curriculum with a basic matrix theory course. The other three sections are small excursions to obtain theorems often not included in such a course. First the fact that every matrix is similar to a matrix in pseudo-diagonal normal form is established. It is the pivotal theorem in the convergence proof for annealing chains which is given in chapter 3. Another fact used in that proof is Gershgorin’s theorem. Its statement and proof is at the end of the third section. That section is mainly devoted to the convergence of matrix expressions and since norms are useful concepts in that context they are introduced there. That section completes the preparation for the next chapter. The definite integral obtained in the fourth section of this chapter is not used before chapter 6. It is included in this chapter because its derivation heavily depends on matrix theory, and quadratic forms in particular.

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.

Many problems that arise in practice are concerned with finding a good or even the best configuration or parameter set from a large set of feasible options. Feasible means that the option has to satisfy a number of rigid requirements. An example of such an optimization problem is to find a minimum weight cylindrical can that must hold a given quantity of liquid. Assuming the weight of the empty can to be proportional to its area, the problem can be formulated as finding the dimensions of a cylinder with a volume c, and the smallest possible perimeter: minimize $$ 2\pi rh + \pi {r^2} $$ while $$ \pi {r^2}h = C $$ and r > 0 The formulation consists of a function to be minimized, the objective function, and a number of constraints. These constraints specify the set of feasible options, in this case the parameter pairs (r,h) that represent cylinders with radius r, height h, and volume c. Feasibility requirements are not always given as explicit constraints. In this example the volume constraint could have been substituted into the objective function.