Global Optima of Lennard-Jones Clusters

This paper summarizes the current state of knowledge concerning putative global minima of the potential energy function for Lennard-Jones clusters, an intensely studied molecular conformation problem. Almost all known exceptions to global optimality of the well-known Northby multilayer icosahedral conformations for microclusters are shown to be minor variants of that geometry. The truly exceptional case of face-centered cubic lattice conformations is examined and connections are made with the macrocluster problem. Several types of algorithms and their limitations are explored, and a new variation on the growth sequence idea is presented and shown to be effective for both small and large clusters.     

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.     

The successive minima in the geometry of numbers and the distinction between algebraic and transcendental numbers

This paper discusses an application of Minkowski's theory of the successive minima in the geometry of numbers to the problem of the approximation of an algebraic or transcendental number a by algebraic numbers. I consider for simplicity only real numbers a. However, it is obvious that an analogous theory can be established for complex numbers, and also for p-adic numbers, as well as for the field of formal ascending or descending Laurent series with coefficients in an arbitrary field.     

A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances

We describe a linear-time algorithm for solving the molecular distance geometry problem with exact distances between all pairs of atoms. This problem needs to be solved in every iteration of general distance geometry algorithms for protein modeling such as the EMBED algorithm by Crippen and Havel (Distance Geometry and Molecular Conformation, Wiley, 1988). However, previous approaches to the problem rely on decomposing an distance matrix or minimizing an error function and require O(n²) to O(³) floating point operations. The linear-time algorithm will provide a much more efficient approach to the problem, especially in large-scale applications. It exploits the problem structure and hence is able to identify infeasible data more easily as well.     

Generalized weak sharp minima in cone-constrained convex optimization on Hadamard manifolds

In this paper, a convex optimization problem with cone constraint (for short, CPC) is introduced and studied on Hadamard manifolds. Some criteria and characterizations for the solution set to be a set of generalized global weak sharp minima, generalized local weak sharp minima and generalized bounded weak sharp minima for (CPC) are derived on Hadamard manifolds.     

Hyperbolic smoothing and penalty techniques applied to molecular structure determination

This work considers the problem of estimating the relative positions of all atoms of a protein, given a subset of all the pair-wise distances between the atoms. This problem is NP-hard, and the usual formulations are nonsmoothed and nonconvex, having a high number of local minima. Our contribution is an efficient method that combines the hyperbolic smoothing and the penalty techniques that are useful in obtaining differentiability and reducing the number of local minima.     

Successive Minima and Best Simultaneous Diophantine Approximations

We study the problem of best approximations of a vector by rational vectors of a lattice whose common denominator is bounded. To this end we introduce successive minima for a periodic lattice structure and extend some classical results from geometry of numbers to this structure. This leads to bounds for the best approximation problem which generalize and improve former results.     

Successive Minima and Best Simultaneous Diophantine Approximations

We study the problem of best approximations of a vector a ? \Bbb Rⁿ\alpha\in{\Bbb R}^n by rational vectors of a lattice L ì \Bbb Rⁿ\Lambda\subset{\Bbb R}^n whose common denominator is bounded. To this end we introduce successive minima for a periodic lattice structure and extend some classical results from geometry of numbers to this structure. This leads to bounds for the best approximation problem which generalize and improve former results.     

Deterministic global optimization in isothermal reactor network synthesis

The reactor network synthesis problem involves the simultaneous determination of the structure and operating conditions of a reactor system to optimize a given performance measure. This performance measure may be the yield of a given product, the selectivity between products, or the overall profitability of the process. The problem is formulated as a nonlinear program (NLP) using a superstructure based method in which plug flow reactors (PFRs) in the structure are modeled using differential-algebraic equations (DAEs). This formulation exhibits multiple local minima. To overcome this, a novel deterministic global optimization method tailored to the special structure and characteristics of this problem will be presented. Examples of isothermal networks will be discussed to show the nature of the local minima and illustrate various components of the proposed approach.     

An Infeasible Point Method for Minimizing the Lennard-Jones Potential

Minimizing the Lennard-Jones potential, the most-studied modelproblem for molecular conformation, is an unconstrained globaloptimization problem with a large number of local minima. In thispaper, the problem is reformulated as an equality constrainednonlinear programming problem with only linear constraints. Thisformulation allows the solution to approached through infeasibleconfigurations, increasing the basin of attraction of the globalsolution. In this way the likelihood of finding a global minimizeris increased. An algorithm for solving this nonlinear program isdiscussed, and results of numerical tests are presented.     

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.     

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.     

Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region

This paper deals with the packing problem of circles and non-convex polygons, which can be both translated and rotated into a strip with prohibited regions. Using the Φ-function technique, a mathematical model of the problem is constructed and its characteristics are investigated. Based on the characteristics, a solution approach to the problem is offered. The approach includes the following methods: an optimization method by groups of variables to construct starting points, a modification of the Zoutendijk feasible direction method to search for local minima and a special non-exhaustive search of local minima to find an approximation to a global minimum. A number of numerical results are given. The numerical results are compared with the best known ones.     

A new transfer principle in the geometry of numbers

In my paper (Proc. Roy. Soc. Edinburgh Sect. A 64 (1956), 223–238), I gave a general transfer principle in the geometry of numbers which consisted of inequalities linking the successive minima of a convex body in n dimensions with those of a convex body in N dimensions where in general N is greater than n. This result contained in particular my earlier theorem on compound convex bodies (Proc. London Math. Soc. (3) 5 (1955), 358–379). In the present paper I apply essentially the same method to prove a new transfer principle which connects the successive minima of a convex body in m dimensions and those of a convex body in n dimensions with the successive minima of a convex body in mn dimensions.     

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

On the structure of the fixed charge transportation problem

This work extends the theory of the fixed charge transportation problem (FCTP), currently based mostly on a forty-year-old publication by Hirsch and Danzig. This paper presents novel properties that need to be considered by those using existing, or those developing new methods for optimizing FCTP. It also defines the problem in an easier way, making it understandable to a wider spectrum of readers. While the analysis is limited to FCTP only, elements of it can easily be extended to the general fixed charge problem. Finally a novel, snap method for finding global minima for FCTPs with large fixed charge coefficients is introduced.     

On Elliptic System Involving Critical Sobolev Exponent and Weights

This paper is devoted to the existence and nonexistence of positive solutions for a semilinear elliptic system involving critical Sobolev exponent and weights. We study the effect of the behavior of weights near their minima on the existence of solutions for the considered problem.     

Strong Fermat Rules for Constrained Set-Valued Optimization Problems on Banach Spaces

In this paper, we propose two kinds of optimality concepts, called the sharp minima and the weak sharp minima, for a constrained set-valued optimization problem. Subsequently, we extend the Fermat rules for the local minima of the constrained set-valued optimization problem to the sharp minima and the weak sharp minima in Banach spaces or Asplund spaces, by means of the Mordukhovich generalized differentiation and the normal cone. As applications, we investigate the generalized inequality systems with constraints, and get some characterizations of error bounds for the constrained generalized inequality systems in convex and nonconvex cases.     

Deterministic Global Optimization in Nonlinear Optimal Control Problems

The accurate solution of optimal control problems is crucial in many areas of engineering and applied science. For systems which are described by a nonlinear set of differential-algebraic equations, these problems have been shown to often contain multiple local minima. Methods exist which attempt to determine the global solution of these formulations. These algorithms are stochastic in nature and can still get trapped in local minima. There is currently no deterministic method which can solve, to global optimality, the nonlinear optimal control problem. In this paper a deterministic global optimization approach based on a branch and bound framework is introduced to address the nonlinear optimal control problem to global optimality. Only mild conditions on the differentiability of the dynamic system are required. The implementa-tion of the approach is discussed and computational studies are presented for four control problems which exhibit multiple local minima.