The String Method as a Dynamical System

This paper is devoted to the theoretical analysis of the zero-temperature string method, a scheme for identifying minimum energy paths (MEPs) on a given energy landscape. By definition, MEPs are curves connecting critical points on the energy landscape which are everywhere tangent to the gradient of the potential except possibly at critical points. In practice, MEPs are mountain pass curves that play a special role, e.g., in the context of rare reactive events that occur when one considers a steepest descent dynamics on the potential perturbed by a small random noise. The string method aims to identify MEPs by moving each point of the curve by steepest descent on the energy landscape. Here we address the question of whether such a curve evolution necessarily converges to an MEP. Surprisingly, the answer is no, for an interesting reason: MEPs may not be isolated, in the sense that there may be families of them that can be continuously deformed into one another. This degeneracy is related to the presence of critical points of Morse index 2 or higher along the MEP. In this paper, we elucidate this issue and completely characterize the limit set of a curve evolving by the string method. We establish rigorously that the limit set of such a curve is again a curve when the MEPs are isolated. We also show under the same hypothesis that the string evolution converges to an MEP. However, we identify and classify situations where the limit set is not a curve and may contain higher dimensional parts. We present a collection of examples where the limit set of a path contains a 2D region, a 2D surface, or a region of an arbitrary dimension up to the dimension of the space. In some of our examples the evolving path wanders around without converging to its limit set. In other examples it fills a region, converging to its limit set, which is not an MEP.     

Existence of stationary solutions and local minima for 2D models of fine structure dynamics

In this paper we study two-dimensional models for the motion of a viscoelastic material with a non-monotone stress-strain relationship. We prove existence of infinitely many stationary solutions to two model problems. This is achieved by constructing sequences of increasingly oscillatory functions, whose limit is a stationary solution. These equilibria may have arbitrarily small energy. We also prove that it is always possible to construct paths in phase space that strictly decrease the energy. This result negates the existence of local minima for the energy and asymptotically stable equilibria. These results are important first steps towards understanding the dynamics of fine structure in more than one dimension.     

A quasi-multistart framework for global optimization of expensive functions using response surface models

We present the AQUARS (A QUAsi-multistart Response Surface) framework for finding the global minimum of a computationally expensive black-box function subject to bound constraints. In a traditional multistart approach, the local search method is blind to the trajectories of the previous local searches. Hence, the algorithm might find the same local minima even if the searches are initiated from points that are far apart. In contrast, AQUARS is a novel approach that locates the promising local minima of the objective function by performing local searches near the local minima of a response surface (RS) model of the objective function. It ignores neighborhoods of fully explored local minima of the RS model and it bounces between the best partially explored local minimum and the least explored local minimum of the RS model. We implement two AQUARS algorithms that use a radial basis function model and compare them with alternative global optimization methods on an 8-dimensional watershed model calibration problem and on 18 test problems. The alternatives include EGO, GLOBALm, MLMSRBF (Regis and Shoemaker in INFORMS J Comput 19(4):497–509, 2007), CGRBF-Restart (Regis and Shoemaker in J Global Optim 37(1):113–135 2007), and multi level single linkage (MLSL) coupled with two types of local solvers: SQP and Mesh Adaptive Direct Search (MADS) combined with kriging. The results show that the AQUARS methods generally use fewer function evaluations to identify the global minimum or to reach a target value compared to the alternatives. In particular, they are much better than EGO and MLSL coupled to MADS with kriging on the watershed calibration problem and on 15 of the test problems.     

Simulation of nuclei morphologies for binary alloy

We study the critical nuclei morphologies of a binary alloy by the string method. The dynamic equation of the string, connecting the metastable phase (liquid) and stable phase (solid), is governed by Helmholtz free energy for the binary alloy system at a given temperature. The stationary string through the critical nucleus (saddle point) is obtained if the relaxation time of the string is sufficiently large. The critical nucleus radius and energy barrier to nucleation of a pure alloy with isotropic interface energy in two and three dimensions are calculated, which are consistent with the classical nucleation theory. The critical nuclei morphologies are sensitive to the anisotropy strength of interface energy and interface thickness of alloy in two and three dimensions. The critical nucleus and energy barrier to nucleation become smaller if the anisotropy strength of the interface energy is increased, which means that it is much easier to form a stable nucleus if the anisotropy of the interface energy is considered.     

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.     

Dynamics on rugged landscapes of energy and ultrametric diffusion

We discuss the interbasin kinetics approximation for random walk on a complex (rugged) landscape of energy. In this approximation the random walk is described by the system of kinetic equations corresponding to transitions between the local minima of energy. If we approximate the transition rates between the local minima by the Arrhenius formula then the system of kinetic equations will be hierarchical. We discuss for a generic landscape of energy the anzats of interbasin kinetics which is equivalent to the ultrametric diffusion generated by an ultrametric pseudodifferential operator.     

Global energy minimisation and cotranslational protein folding of HP models

The globally minimum energy configurations of simple HP lattice models (which use only two amino acid types, positioned on the vertices of a square lattice) of proteins have been established for short sequences. Here we investigate the folding of such proteins to this globally minimum energy configuration, both cotranslationally (as they are manufactured, sequentially, in the ribosome) and starting from a fully extended state. In order to do this we model the folding process and develop a heuristic method for finding local energy minima. Two main results emerge. First, some sequences do fold better cotranslationally than from a fully extended state and second, this can be due to cotranslational folding leading to an initial local energy minimum from which movement to the global minimum is efficient. Sequences for which this is true tend to have a higher density of hydrophobic residues at the start than at the finish. Structural properties of sequences that fold better cotranslationally than from a fully extended state are also identified.     

Iterative Convex Quadratic Approximation for Global Optimization in Protein Docking

An algorithm for finding an approximate global minimum of a funnel shaped function with many local minima is described. It is applied to compute the minimum energy docking position of a ligand with respect to a protein molecule. The method is based on the iterative use of a convex, general quadratic approximation that underestimates a set of local minima, where the error in the approximation is minimized in the L¹ norm. The quadratic approximation is used to generate a reduced domain, which is assumed to contain the global minimum of the funnel shaped function. Additional local minima are computed in this reduced domain, and an improved approximation is computed. This process is iterated until a convergence tolerance is satisfied. The algorithm has been applied to find the global minimum of the energy function generated by the Docking Mesh Evaluator program. Results for three different protein docking examples are presented. Each of these energy functions has thousands of local minima. Convergence of the algorithm to an approximate global minimum is shown for all three examples.     

Growth of Nanophase Clusters and Potential Energy Minima: Hysteresis, Oscillations, and Phase Transitions

The structures of small Lennard-Jones clusters (local and global minima) in the range n = 30 - 55 atoms are investigated during growth by random atom deposition using Monte Carlo simulations. The cohesive energy, average coordination number, and bond angles are calculated at different temperatures and deposition rates. Deposition conditions which favor thermodynamically stable (global minima) and metastable (local minima) are determined. We have found that the transition from polyicosahedral to quasicrystalline structures during cluster growth exhibits hysteresis at low temperatures. A minimum critical size is required for the evolution of the quasicrystalline family, which is larger than the one predicted by thermodynamics and depends on the temperature and the deposition rate. Oscillations between polyicosahedral and quasicrystalline structures occur at high temperatures in a certain size regime. Implications for the applicability of global optimization techniques to cluster structure determination are also discussed.     

Minima, pentes et algèbre tensorielle

Slopes of an adelic vector bundle exhibit a behaviour akin to successive minima. Comparisons between the two amount to a Siegel lemma. Here we use Zhang’s version for absolute minima over the algebraic numbers. We prove a Minkowski-Hlawka theorem in this context. We also study the tensor product of two hermitian bundles bounding both its absolute minimum and maximal slope, thus improving an estimate of Chen. We further include similar inequalities for exterior and symmetric powers, in terms of some lcm of multinomial coefficients.     

Challenges of continuous global optimization in molecular structure prediction

The molecular geometry, the three dimensional arrangement of atoms in space, is a major factor determining the properties and reactivity of molecules, biomolecules and macromolecules. Computation of stable molecular conformations can be done by locating minima on the potential energy surface (PES). This is a very challenging global optimization problem because of extremely large numbers of shallow local minima and complicated landscape of PES. This paper illustrates the mathematical and computational challenges on one important instance of the problem, computation of molecular geometry of oligopeptides, and proposes the use of the Extended Cutting Angle Method (ECAM) to solve this problem.     

Global optimization by random perturbation of the gradient method with a fixed parameter

The paper deals with the global minimization of a differentiable cost function mapping a ball of a finite dimensional Euclidean space into an interval of real numbers. It is established that a suitable random perturbation of the gradient method with a fixed parameter generates a bounded minimizing sequence and leads to a global minimum: the perturbation avoids convergence to local minima. The stated results suggest an algorithm for the numerical approximation of global minima: experiments are performed for the problem of fitting a sum of exponentials to discrete data and to a nonlinear system involving about 5000 variables. The effect of the random perturbation is examined by comparison with the purely deterministic gradient method.     

A tensor model for liquid crystals on a spherical surface

Rod-like molecules confined on a spherical surface can organize themselves into nematic liquid crystal phases. This can give rise to novel textures displayed on the surface, which has been observed in experiments. An important theoretical question is how to find and predict these textures. Mathematically, a stable configuration of the nematic fluid corresponds to a local minimum in the free energy landscape. By applying Taylor expansion and Bingham approximation to a general molecular model, we obtain a closed-form tensor model, which gives a free energy form that is different from the classic Landau-de Gennes model. Based on the tensor model, we implement an efficient numerical algorithm to locate the local minimum of the free energy. Our model successfully predicts the splay, tennis-ball and rectangle textures. Among them, the tennis-ball configuration has the lowest free energy.     

Residual capacities of uniaxially compressed,delaminated composite panels

The mechanical buckling and postbuckling behaviour of a delaminated panel under uniaxial compression is investigated using a semi-analytical geometrically nonlinear panel model. A Rayleigh-Ritz procedure based on trigonometric displacement functions is used in conjunction with minimum energy principles to ascertain the mechanical response of the panels. The model includes the effect of delamination propagation resulting from the buckling of the laminates utilizing a discrete cohesive zone model. With the model developed, a detailed assessment of the residual capacity of the panel is provided due to its capability of tracing the equilibrium paths far into the postbuckling range. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Packing cylinders and rectangular parallelepipeds with distances between them into a given region

This paper considers the problem of packing cylinders and parallelepipeds into a given region so that the height of the occupied part of the region is minimal and the distances between each pair of items, and the distance between each packed item and the frontier of the region must be greater than or equal to given distances. A mathematical model of the problem is built and some characteristics of the mathematical model are investigated. Methods for fast construction of starting points, searching for local minima, and a special non-exhaustive search of local minima to obtain good approximations to a global minimum are offered. A numerical example is given. Runtimes to obtain starting points, local minima and approximations to a global minimum are adduced.     

Energy Landscapes for the Self-Assembly of Supramolecular Polyhedra

We develop a mathematical model for the energy landscape of polyhedral supramolecular cages recently synthesized by self-assembly (Sun et al. in Science 328:1144–1147, 2010). Our model includes two essential features of the experiment: (1) geometry of the organic ligands and metallic ions; and (2) combinatorics. The molecular geometry is used to introduce an energy that favors square-planar vertices (modeling \(\mathrm {Pd}^{2+}\) ions) and bent edges with one of two preferred opening angles (modeling boomerang-shaped ligands of two types). The combinatorics of the model involve two-colorings of edges of polyhedra with four-valent vertices. The set of such two-colorings, quotiented by the octahedral symmetry group, has a natural graph structure and is called the combinatorial configuration space. The energy landscape of our model is the energy of each state in the combinatorial configuration space. The challenge in the computation of the energy landscape is a combinatorial explosion in the number of two-colorings of edges. We describe sampling methods based on the symmetries of the configurations and connectivity of the configuration graph. When the two preferred opening angles encompass the geometrically ideal angle, the energy landscape exhibits a very low-energy minimum for the most symmetric configuration at equal mixing of the two angles, even when the average opening angle does not match the ideal angle.     

Optimal egress time calculation and path generation for large evacuation networks

Finding the optimal clearance time and deciding the path and schedule of evacuation for large networks have traditionally been computationally intensive. In this paper, we propose a new method for finding the solution for this dynamic network flow problem with considerably lower computation time. Using a three phase solution method, we provide solutions for required clearance time for complete evacuation, minimum number of evacuation paths required for evacuation in least possible time and the starting schedules on those paths. First, a lower bound on the clearance time is calculated using minimum cost dynamic network flow model on a modified network graph representing the transportation network. Next, a solution pool of feasible paths between all O-D pairs is generated. Using the input from the first two models, a flow assignment model is developed to select the best paths from the pool and assign flow and decide schedule for evacuation with lowest clearance time possible. All the proposed models are mixed integer linear programing models and formulation is done for System Optimum (SO) scenario where the emphasis is on complete network evacuation in minimum possible clearance time without any preset priority. We demonstrate that the model can handle large size networks with low computation time. A numerical example illustrates the applicability and effectiveness of the proposed approach for evacuation.     

Practical estimation of a splitting parameter for a spectral method for the ternary Cahn–Hilliard system with a logarithmic free energy

We propose a practical estimation of a splitting parameter for a spectral method for the ternary Cahn–Hilliard system with a logarithmic free energy. We use Eyre's convex splitting scheme for the time discretization and a Fourier spectral method for the space variables. Given an absolute temperature, we find composition values that make the total free energy be minimum. Then, we find the splitting parameter value that makes the two split homogeneous free energies be convex on the neighborhood of the local minimum concentrations. For general use, we also propose a sixth‐order polynomial approximation of the minimum concentration and derive a useful formula for the practical estimation of the splitting parameter in terms of the absolute temperature. The numerical tests are phase separation and total energy decrease with different temperature values. The linear stability analysis shows a good agreement between the exact and numerical solutions with an optimal value s. Various computational experiments confirm that the proposed splitting parameter estimation gives stable numerical results. Copyright © 2016 John Wiley & Sons, Ltd.     

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms

In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented. The methodology utilizes a Delaunay triangulation to represent surface fire spread within the landscape. A procedure to construct the graph and estimate the rate of spread along the edges of a network is discussed. After the Delaunay data structure is constructed, a two pass shortest path algorithm is incorporated to estimate the minimum travel time paths and fire arrival times. Experimental results are also included.     

Modelling and remodelling of biological tissue in the framework of continuum biomechanics

A biological tissue in general is formed by cells, extracellular matrix (ECM) and fluids. Consequently, its overall material behaviour results from its components and their interaction among each other. Furthermore, in case of living tissues, the material properties do not remain constant but naturally change due to adaptation processes or diseases. In the context of the Theory of Porous Media (TPM), a continuum-mechanical model is introduced to describe the complex fluid-structure interaction in biological tissue on a macroscopic scale. The tissue is treated as an aggregate of two immiscible constituents, where the cells and the ECM are summarised to a solid phase, whereas the fluid phase represents the extracellular and interstitial liquids as well as necrotic debris and cell or matrix precursors in solution. The growth and remodelling processes are described by a distinct mass exchange between the fluid and solid phase, which also results in a change of the constituent material behaviour. To furthermore guarantee the compliance with the entropy principle, the growth energy is introduced as an additional quantity. It measures the average of chemical energy available for cell metabolism, and thus, controls the growth and remodelling processes. To set an example, the presented model is applied for the simulation of the early stages of avascular tumour growth in the framework of the finite element method (FEM). (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)