Optimization Algorithms Based on Renormalization Group
Naoki Kawashima · Progress of Theoretical Physics Supplement · 2000
Global changes of states are of crucial importance in optimization algorithms. We review some heuristic algorithms in which global updates are realized by a sort of real-space renormalization group transformation. Emphasis is on the relationship between the structure of low-energy excitations and “block-spins” appearing in the algorithms. We also discuss the implication of existence of a finite-temperature phase transition on the computational complexity of the ground-state problem.