The Leary Tetrahedron: Finding New Approaches to Global Optimization

magine yourself in hilly country, looking for the deepest valley. You may find it instantly by just scanning the landscape, but chances are that you must traipse over hill and dale, taking measurements. Many scientific problems involve searching some mathematical equivalent of hilly country, such as an "energy landscape." Protein scientists, for example, find that the basic 3-D structure of a protein is at a global minimum on its potential energy surface or landscape. They would use optimization to predict how a protein goes from the high-energy state of an unfolded sequence to the lowest energy, native, folded state.

A NEW APPROACH

HUNTING THE GLOBAL OPTIMUM

PINBALL VERSUS PACHINKO

A NEW APPROACH

Robert H. Leary, an applied mathematician and senior staff scientist at SDSC, has achieved a new result in global optimization (Figure 1). "The simplest representation of the optimization problem is found in the Lennard-Jones microcluster," Leary said. "What I've done is find a new way of arranging 98 atoms in such a cluster, and it has perfect tetrahedral symmetry."

Most global optima for fewer than 150 atoms are icosahedral in shape. Only a few have been found that are nonicosahedral--notably a truncated octahedron of 38 atoms, a "Marks decahedron" of 75 atoms, and now the Leary structure of 98 atoms.

Lennard-Jones (LJ) clusters--named for English theoretical chemist Sir John Lennard-Jones (1894– 1954)--contain neutral atoms. They're found in a few physical systems, specifically, low-temperature atomic clusters of heavy, rare-gases such as argon, krypton, and xenon. Other kinds of clusters also provide tests of optimization, but because LJ clusters allow comparison of calculations with lab measurements, the LJ model of interatomic interactions yields a way to check results. It has become a benchmark for global optimization algorithms.

The LJ potential function for a pair of neutral atoms is a simple curve, whose overall minimum is easy to pick out. The superposition of many such curves for each atom pair in a cluster produces a complex energy landscape with many local minima. For LJ problems, a cluster of more than 20 atoms will have millions of local minima.

REFERENCES

Wales, D.J., and Scheraga, H. (1999): Global optimization of clusters, crystals, and biomolecules, Science 285, 1368-1372.

Leary, R.H., and Doye, J.A. (1999): A new tetrahedral global minimum for the 98-atom Lennard-Jones cluster, Physical Review E (in press).

In this arrangement of 98 atoms, all atoms of the same color have the same energy and occupy symmetrically equivalent positions in the structure.

HUNTING THE GLOBAL OPTIMUM

For a set of similar atoms in a cluster, there is a global minimum-energy arrangement. Mathematicians try to find these, using algorithms like steepest descent, conjugate gradient, and Newton's method. "It's easy to do an efficient local search to find a nearby local minimum," Leary said. "But that method may miss a distant, lower minimum."

Leary's algorithm is a variant of a Monte Carlo approach called "basin hopping." Given a chosen local minimum, a random step away is "proposed" and a local minimization procedure is started where the step lands. This leads to a new point on the surface, higher or lower in energy than the starting point. The step is taken if the new energy is lower. If it isn't, a "Metropolis" criterion is invoked--a random number is compared to an expression containing both the new and old energies. The Metropolis step is taken only if the expression is less than the random number.

"Basically, the basin-hopping algorithm drives downhill, but the Metropolis criterion assures that it will go uphill some of the time to avoid getting trapped," Leary said. He modified the code to accept only downhill steps and increased the number searches for the next step.

PINBALL VERSUS PACHINKO

The old algorithm differs from the new as a Western pinball machine differs from a Japanese pachinko game. "Pinball sends out one ball. If you use the flippers skillfully, you can make it go uphill occasionally and keep it in play longer for more points in the game," Leary said. "But pachinko machines send out many balls that all fall in strictly descending paths. With enough balls, at least one is likely to fall in the highest payoff slot." The use of such algorithmic tradeoffs in investigating simple LJ clusters points to the possible validity of similarly mixed approaches to more complicated protein-folding problems, he noted.

For 98 atoms, the code generates sequences of about 20 descending moves ending in a low-lying local minimum. As sequences progress, it's harder to find descending moves, so the process uses millions of local optimizations. The 98-atom optimization problem took a week on one processor as Leary pursued calculations for different numbers of atoms on a Sun HPC 10000 with 16 333-MHz Ultra II processors. The new Sun HPC 10000 machine has 64 400-MHz processors, with 64 gigabytes of memory, so the algorithm will go much faster.

"What we've learned is not just the solution of the 98-atom LJ cluster," Leary said, "but rather more about the various solutions that can be found with different approaches, in complex energy landscapes."
--MM *