Global minimum potential energy conformations of small molecules

A global optimization algorithm is proposed for finding the global minimum potential energy conformations of small molecules. The minimization of the total potential energy is formulated on an independent set of internal coordinates involving only torsion (dihedral) angles. Analytical expressions for the Euclidean distances between non-bonded atoms, which are required for evaluating the individual pairwise potential terms, are obtained as functions of bond lengths, covalent bond angles, and torsion angles. A novel procedure for deriving convex lower bounding functions for the total potential energy function is also introduced. These underestimating functions satisfy a number of important theoretical properties. A global optimization algorithm is then proposed based on an efficient partitioning strategy which is guaranteed to attain -convergence to the global minimum potential energy configuration of a molecule through the solution of a series of nonlinear convex optimization problems. Moreover, lower and upper bounds on the total finite number of required iterations are also provided. Finally, this global optimization approach is illustrated with a number of example problems.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

Global optimization for molecular conformation problems

A primal-relaxed dual global optimization algorithm is presented along with an extensive review for finding the global minimum energy configurations of microclusters composed by particles interacting with any type of two-body central forces. First, the original nonconvex expression for the total potential energy is transformed to the difference of two convex functions (DC transformation) via an eigenvalue analysis performed for each pair potential that constitutes the total potential energy function. Then, a decomposition strategy based on the GOP algorithm [1–4] is designed to provide tight upper and lower bounds on the global minimum through the solutions of a sequence of relaxed dual subproblems. A number of theoretical results are included which expedite the computational effort by exploiting the special mathematical structure of the problem. The proposed approach attains-convergence to the global minimum in a finite number of iterations. Based on this procedure global optimum solutions are generated for small Lennard-Jones and Morse (a=3) microclustersn7. For larger clusters (8N24 for Lennard-Jones and 8N30 for Morse), tight lower and upper bounds on the global solution are provided which serve as excellent initial points for local optimization approaches.     

Conformational searches for the global minimum of protein models

The conformational space of two protein structures has been examined using a stochastic search method in an effort to locate the global minimum conformation. In order to reduce this optimization problem to a tractable level, we have implemented a simplified force field representation of the protein structure that drastically reduces the degrees of freedom. The model replaces each ammo acid (containing many atoms) with a single sphere centered on the C position. These spheres are connected by virtual bonds, producing a string of beads model of the peptide chain. This model has been coupled with our stochastic search method to globally optimize the conformation of two common structural motifs found in proteins, a 22-residue -helical hairpin and a 46-residue -barrel. The search method described further reduces the optimization problem by taking advantage of the rotational isomerisms associated with molecular conformations and stochastically explores the energy surface using internal, torsional degrees of freedom. The approach proved to be highly efficient for globally optimizing the conformation of the -helical hairpin and -barrel structure on a moderately powered workstation. The results were further verified by applying variations in the search strategy that probed the low energy regions of conformational space near the suspected global minimum. Since this method also provides information regarding the low energy conformers, we have presented an analysis of the structures populated, and brief comparisons with other work. Finally, we applied the method to globally optimize the conformation of a 9-residue peptide fragment using a popular all-atom representation and successfully located the global minimum consistent with results from previous work.     

A GA-Simplex Hybrid Algorithm for Global Minimization of Molecular Potential Energy Functions

In this paper we propose a hybrid genetic algorithm for minimizing molecular potential energy functions. Experimental evidence shows that the global minimum of the potential energy of a molecule corresponds to its most stable conformation, which dictates its properties. The search for the global minimum of a potential energy function is very difficult since the number of local minima grows exponentially with molecule size. The proposed approach was successfully applied to two cases: (i) a simplified version of more general molecular potential energy functions in problems with up to 100 degrees of freedom, and (ii) a realistic potential energy function modeling two different molecules.     

An improved hybrid global optimization method for protein tertiary structure prediction

First principles approaches to the protein structure prediction problem must search through an enormous conformational space to identify low-energy, near-native structures. In this paper, we describe the formulation of the tertiary structure prediction problem as a nonlinear constrained minimization problem, where the goal is to minimize the energy of a protein conformation subject to constraints on torsion angles and interatomic distances. The core of the proposed algorithm is a hybrid global optimization method that combines the benefits of the αBB deterministic global optimization approach with conformational space annealing. These global optimization techniques employ a local minimization strategy that combines torsion angle dynamics and rotamer optimization to identify and improve the selection of initial conformations and then applies a sequential quadratic programming approach to further minimize the energy of the protein conformations subject to constraints. The proposed algorithm demonstrates the ability to identify both lower energy protein structures, as well as larger ensembles of low-energy conformations.     

A Generic Global Optimization Algorithm for the Chemical and Phase Equilibrium Problem

This paper addresses the problem of finding the number, K, of phases present at equilibrium and their composition, in a chemical mixture of n _s substances. This corresponds to the global minimum of the Gibbs free energy of the system, subject to constraints representing m _b independent conserved quantities, where m _b=n _s when no reaction is possible and m _b n _e +1 when reaction is possible and n _e is the number of elements present. After surveying previous work in the field and pointing out the main issues, we extend the necessary and sufficient condition for global optimality based on the reaction tangent-plane criterion, to the case involving different thermodynamical models (multiple phase classes). We then present an algorithmic approach that reduces this global optimization problem (involving a search space of m _b(n _s-1) dimensions) to a finite sequence of local optimization steps inK(n _s-1) -space, K m _b, and global optimization steps in (n _s-1)-space. The global step uses the tangent-plane criterion to determine whether the current solution is optimal, and, if it is not, it finds an improved feasible solution either with the same number of phases or with one added phase. The global step also determines what class of phase (e.g. liquid or vapour) is to be added, if any phase is to be added. Given a local minimization procedure returning a Kuhn–Tucker point and a global optimization procedure (for a lower-dimensional search space) returning a global minimum, the algorithm is proved to converge to a global minimum in a finite number of the above local and global steps. The theory is supported by encouraging computational results.     

Molecular conformation of n-alkanes using terrain/funneling methods

Understanding molecular conformation is a first step in understanding the waxing (or formation of crystals) of petroleum fuels. In this work, we study the molecular conformation of typical fuel oils modeled as pure n-alkanes. A multi-scale global optimization methodology based on terrain methods and funneling algorithms is used to find minimum energy molecular conformations of united atom n-alkane models for diesel, home heating, and residual fuel oils. The terrain method is used to gather average gradient and average Hessian matrix information at the small length scale while funneling is used to generate conformational changes at the large length scale that drive iterates to a global minimum on the potential energy surface. In addition, the funneling method uses a mixture of average and point-wise derivative information to produce a monotonically decreasing sequence of objective function values and to avoid getting trapped at local minima on the potential energy surface. Computational results clearly show that the calculated united atom molecular conformations are comprised of zigzag structure with considerable wrapping at the ends of the molecule and that planar zigzag conformations usually correspond to saddle points. Furthermore, the numerical results clearly demonstrate that our terrain/funneling approach is robust and fast.     

Parallel continuation-based global optimization for molecular conformation and protein folding

This paper presents our recent work on developing parallel algorithms and software for solving the global minimization problem for molecular conformation, especially protein folding. Global minimization problems are difficult to solve when the objective functions have many local minimizers, such as the energy functions for protein folding. In our approach, to avoid directly minimizing a difficult function, a special integral transformation is introduced to transform the function into a class of gradually deformed, but smoother or easier functions. An optimization procedure is then applied to the new functions successively, to trace their solutions back to the original function. The method can be applied to a large class of nonlinear partially separable functions including energy functions for molecular conformation and protein folding. Mathematical theory for the method, as a special continuation approach to global optimization, is established. Algorithms with different solution tracing strategies are developed. Different levels of parallelism are exploited for the implementation of the algorithms on massively parallel architectures.     

On the dynamics of fine structure

Summary We investigate models for the dynamical behavior of mechanical systems that dissipate energy as timet increases. We focus on models whose underlying potential energy functions do not attain a minimum, possessing minimizing sequences with finer and finer structure that converge weakly to nonminimizing states. In Model 1 the evolution is governed by a nonlinear partial differential equation closely related to that of one-dimensional viscoelasticity, the underlying static problem being of mixed type. In Model 2 the equation of motion is an integro—partial differential equation obtained from that in Model 1 by an averaging of the nonlinear term; the corresponding potential energy is nonlocal.After establishing global existence and uniqueness results, we consider the longtime behavior of the systems. We find that the two systems differ dramatically. In Model 1, for no solution does the energy tend to its global minimum ast . In Model 2, however, a large, dense set of solutions realize global minimizing sequences; in this case we are able to characterize, asymptotically, how energy escapes to infinity in wavenumber space in a manner that depends upon the smoothness of initial data. We also briefly discuss a third model that shares the stationary solutions of the second but is a gradient dynamical system.The models were designed to provide insight into the dynamical development of finer and finer microstructure that is observed in certain material phase transformations. They are also of interest as examples of strongly dissipative, infinite-dimensional dynamical systems with infinitely many unstable modes, the asymptotic fate of solutions exhibiting in the case of Model 2 an extreme sensitivity with respect to the initial data.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

Dynamics of Peptide Folding: Transition States and Reaction Pathways of Solvated and Unsolvated Tetra-Alanine

A new approach is proposed for enclosing all stationary states, including saddle points of all orders, of a potential energy surface based on the BB deterministic branch and bound global optimization algorithm. This method is based on rigorous optimization methods and offers a theoretical guarentee of enclosing all solutions to the equation V=0. This method is applied to the ECEPP/3 (Empirical Conformational Energy Program for Peptides) potential energy surfaces of unsolvated and solvated tetra-alanine. By analyzing the topography of the potential energy surfaces, we calculate reaction pathways, transition rate matrices, time-evolution of occupation probabilities, and rate disconnectivity graphs, and we identify appropriate criteria for the selection of a reaction coordinate.     

Finding all solutions of nonlinearly constrained systems of equations

A new approach is proposed for finding all-feasible solutions for certain classes of nonlinearly constrained systems of equations. By introducing slack variables, the initial problem is transformed into a global optimization problem (P) whose multiple global minimum solutions with a zero objective value (if any) correspond to all solutions of the initial constrained system of equalities. All-globally optimal points of (P) are then localized within a set of arbitrarily small disjoint rectangles. This is based on a branch and bound type global optimization algorithm which attains finite-convergence to each of the multiple global minima of (P) through the successive refinement of a convex relaxation of the feasible region and the subsequent solution of a series of nonlinear convex optimization problems. Based on the form of the participating functions, a number of techniques for constructing this convex relaxation are proposed. By taking advantage of the properties of products of univariate functions, customized convex lower bounding functions are introduced for a large number of expressions that are or can be transformed into products of univariate functions. Alternative convex relaxation procedures involve either the difference of two convex functions employed in BB [23] or the exponential variable transformation based underestimators employed for generalized geometric programming problems [24]. The proposed approach is illustrated with several test problems. For some of these problems additional solutions are identified that existing methods failed to locate.     

αBB: A global optimization method for general constrained nonconvex problems

A branch and bound global optimization method,BB, for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e. bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the parameter as defined in [17] to underestimate nonconvex terms of generic structure. The proposed branch and bound type algorithm attains finite-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method,BB, is implemented in C and tested on a variety of example problems.     

On a Branch and Bound Algorithm for the Solution of a Family of Softening Material Problems of Mechanics with Applications to the Analysis of Metallic Structures

The variational formulation of mechanical problems involving nonmonotone,possibly multivalued, material or boundary laws leads to hemivariationalinequalities. The solutions of the hemivariational inequalities constitutesubstationarity points of the related energy (super)potentials. For theircomputation convex and global optimization algorithms have been proposedinstead of the earlier nonlinear optimization methods, due to the lack ofsmoothness and convexity of the potential. In earlier works one of us hasproposed an approach based on the decomposition of the solutions space intoconvex parts resulting in a sequence of convex optimization subproblems withdifferent feasible sets. In this case nonconvexity of the potential wasattributed to (generalized) gradient jumps. In order to treat softeningmaterial effects, in the present paper this method is extended to cover alsoenergy functionals where nonconvexity is caused by the existence of concavesections. The nonconvex minimization problem is formulated as d.c.(difference convex) minimization and an algorithm of the branch and boundtype based on simplex partitions is adapted for its treatment. Thepartitioning scheme employed here is adapted to the large dimension of theproblem and the approximation steps are equivalent to convex minimizationsubproblems of the same structure as the ones arising in unilateral problemsof mechanics. The paper concludes with a numerical example and a discussionof the properties and the applicability of the method.     

Efficient Algorithms for Large Scale Global Optimization: Lennard-Jones Clusters

A stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of a cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed incorporates within an already existing and quite successful method, monotonic basin hopping, a two-phase local search procedure which is capable of significantly enlarging the basin of attraction of the global optimum. The experiments reported confirm the considerable advantages of this approach, in particular for all those cases which are considered in the literature as the most challenging ones, namely 75, 98, 102 atoms. While being capable of discovering all putative global optima in the range considered, the method proposed improves by more than two orders of magnitude the speed and the percentage of success in finding the global optima of clusters of 75, 98, 102 atoms.     

On the Efficiency of a Global Non-differentiable Optimization Algorithm Based on the Method of Optimal Set Partitioning

The examined algorithm for global optimization of the multiextremal non-differentiable function is based on the following idea: the problem of determination of the global minimum point of the function f(x) on the set (f(x) has a finite number of local minima in this domain) is reduced to the problem of finding all local minima and their attraction spheres with a consequent choice of the global minimum point among them. This reduction is made by application of the optimal set partitioning method. The proposed algorithm is evaluated on a set of well-known one-dimensional, two-dimensional and three-dimensional test functions. Recommendations for choosing the algorithm parameters are given.     

New results for molecular formation under pairwise potential minimization

We establish new lower bounds on the distance between two points of a minimum energy configuration of N points in ℝ³ interacting according to a pairwise potential function. For the Lennard-Jones case, this bound is 0.67985 (and 0.7633 in the planar case). A similar argument yields an estimate for the minimal distance in Morse clusters, which improves previously known lower bounds. Moreover, we prove that the optimal configuration cannot be two-dimensional, and establish an upper bound for the distance to the nearest neighbour of every particle, which depends on the position of this particle. On the boundary of the optimal configuration polytope, this is unity while in the interior, this bound depends on the potential function. In the Lennard-Jones case, we get the value . Also, denoting by V _N the global minimum in an N point minimum energy configuration, we prove in Lennard-Jones clusters for all N≥2, while asymptotically holds (as opposed to in the planar case, confirming non-planarity for large N).     

Global Optimization on Funneling Landscapes

Molecular conformation problems arising in computational chemistry require the global minimization of a non-convex potential energy function representing the interactions of, for example, the component atoms in a molecular system. Typically the number of local minima on the potential energy surface grows exponentially with system size, and often becomes enormous even for relatively modestly sized systems. Thus the simple multistart strategy of randomly sampling local minima becomes impractical. However, for many molecular conformation potential energy surfaces the local minima can be organized by a simple adjacency relation into a single or at most a small number of funnels. A distinguished local minimum lies at the bottom of each funnel and a monotonically descending sequence of adjacent local minima connects every local minimum in the funnel with the funnel bottom. Thus the global minimum can be found among the comparatively small number of funnel bottoms, and a multistart strategy based on sampling funnel bottoms becomes viable. In this paper we present such an algorithm of the basin-hopping type and apply it to the Lennard–Jones cluster problem, an intensely studied molecular conformation problem which has become a benchmark for global optimization algorithms. Results of numerical experiments are presented which confirm both the multifunneling character of the Lennard–Jones potential surface as well as the efficiency of the algorithm. The algorithm has found all of the current putative global minima in the literature up to 110 atoms, as well as discovered a new global minimum for the 98-atom cluster of a novel geometrical class.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.