Method of Constrained Global Optimization

Eric Lewin Altschuler, Timothy J. Williams, Edward R. Ratner, Farid Dowla, and Frederick Wooten

Lawrence Livermore National Laboratory, PO Box 808, Livermore, CA 94551
Dept. of Applied Physics, Stanford University, Stanford, CA 94305
Dept. of Applied Science, U. C. Davis/Livermore, PO Box 808, Livermore CA 94551

March 22, 1994

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.

PACS numbers: 02.60.Pn, 02.70.-c, 02.70.Lq, 41.20.Cv

Timothy J. Williams
Thu Jan 4 16:47:51 MST 1996