Part IV Toward Structure Theory and Real Understanding
2002
Part IV continues our development of the physical understanding one can gain about annealing algorithms. The theory developed here sheds a great deal of light on the methods presented in Part III and is, we believe, indispensable for the ultimate understanding that can bring this subject from the realm of heuristics to the realm of provably optimal algorithms. This latter realm is likely to divide the family of global optimization problems into classes based on structural features of the problem and the best approach is likely to depend on class. This motivates our belief that the important next step for global optimization will require a better understanding of the geometrical structure of complex landscapes. Chapter 15 discusses how this structure can be analyzed, emphasizing the issues of coarse graining and of how the multitude of traps invariably present in such landscapes should be characterized. In our discussion we use a mixture of simple arguments based on toy models and numerical evidence pertaining to real examples. The Appendix to Chapter 15 is meant to convey some intuition regarding entropic barriers, an issue of considerable importance in high-dimensional problems. Chapter 16 uses the concepts and results discussed in Chapter 15 to ponder the puzzling question of why annealing works at all.