We provide some tests of the convex global underestimator (CGU) algorithm,
which aims to find global minima on funnel-shaped energy landscapes. We use
two different potential functions-the reduced Lennard-Jones cluster potent
ial, and the modified Sun protein folding potential, to compare the CGU alg
orithm with the simplest versions of the traditional trajectory-based searc
h methods, simulated annealing (SA), and Monte Carlo (MC). For both potenti
als, the CGU reaches energies lower on the landscapes than both SA and MC,
even when SA and MC are given the same number of starting points as in a fu
ll CGU run or when all methods are given the same amount of computer time.
The CGU consistently finds the global minima of the Lennard-Jones potential
for all cases with up to at least n = 30 degrees of freedom. Finding the g
lobal or near-global minimum in the CGU method requires polynomial time [sc
aling between O(n(3)) and O(n(4))], on average. (C) 1999 John Wiley & Sons,
Inc.