Method of constrained global optimization

Abstract

We present a new method for optimization: constrained global optimization (CGO). CGO iteratively uses a Glauber spin flip probability and the Metropolis algorithm. The spin flip probability allows changing only the values of variables contributing excessively to the function to be minimized. We illustrate CGO with two problems---Thomson's problem of finding the minimum-energy configuration of unit charges on a spherical surface, and a problem of assigning offices---for which CGO finds better minima than other methods. We think CGO will apply to a wide class of optimization problems.