SDSC RESEARCH  Contents  Next  
The Leary Tetrahedron: Finding New Approaches to Global Optimization 

FEATURED Robert H. Leary, SDSC 
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 3D 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 highenergy state of an unfolded sequence to the lowest energy, native, folded state. 
A NEW APPROACHHUNTING THE GLOBAL OPTIMUMPINBALL VERSUS PACHINKO 
A NEW APPROACHRobert 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 LennardJones 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 nonicosahedralnotably a truncated octahedron of 38 atoms, a "Marks decahedron" of 75 atoms, and now the Leary structure of 98 atoms. LennardJones (LJ) clustersnamed for English theoretical chemist Sir John LennardJones (1894– 1954)contain neutral atoms. They're found in a few physical systems, specifically, lowtemperature atomic clusters of heavy, raregases 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. 
Top Contents  Next
REFERENCES Wales, D.J., and Scheraga, H. (1999): Global optimization of clusters, crystals, and biomolecules, Science 285, 13681372. Leary, R.H., and Doye, J.A. (1999): A new tetrahedral global minimum for the 98atom LennardJones 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 OPTIMUMFor a set of similar atoms in a cluster, there is a global minimumenergy 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 invokeda 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 basinhopping 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. 
Top Contents  Next 
PINBALL VERSUS PACHINKOThe 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 proteinfolding problems, he noted. For 98 atoms, the code generates sequences of about 20 descending moves ending in a lowlying local minimum. As sequences progress, it's harder to find descending moves, so the process uses millions of local optimizations. The 98atom optimization problem took a week on one processor as Leary pursued calculations for different numbers of atoms on a Sun HPC 10000 with 16 333MHz Ultra II processors. The new Sun HPC 10000 machine has 64 400MHz processors, with 64 gigabytes of memory, so the algorithm will go much faster. "What we've learned is not just the solution of the 98atom LJ cluster," Leary said, "but rather more about the various solutions that can be found with different approaches, in complex energy landscapes." 
Top Contents  Next 