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.     

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.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

Asynchronously parallel optimization solver for finding multiple minima

We propose and analyze an asynchronously parallel optimization algorithm for finding multiple, high-quality minima of nonlinear optimization problems. Our multistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that when there are finitely many minima, the algorithm almost surely starts a finite number of local optimization runs and identifies every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a Python implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability is shown to scale well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to perform the function evaluation is highly variable. An implementation of the algorithm is available in the libEnsemble library at https://github.com/Libensemble/libensemble.     

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.     

Sufficient conditions for solving linearly constrained separable concave global minimization problems

A concave function defined on a polytope may have many local minima (in fact every extreme point may be a local minimum). Sufficient conditions are given such that if they are satisfied at a point, this point is known to be a global minimum. It is only required to solve a single linear program to test whether the sufficient conditions are satisfied. This test has been incorporated into an earlier algorithm to give improved performance. Computational results presented show that these sufficient conditions are satisfied for certain types of problems and may substantially reduce the effort needed to find and recognize a global minimum.     

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.     

Global Minimization via Piecewise-Linear Underestimation

Given a function on Rⁿ with many multiple local minima we approximate it from below, via concave minimization, with a piecewise-linear convex function by using sample points from the given function. The piecewise-linear function is then minimized using a single linear program to obtain an approximation to the global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.57%, of the global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly.     

Globally-biased Disimpl algorithm for expensive global optimization

Direct-type global optimization algorithms often spend an excessive number of function evaluations on problems with many local optima exploring suboptimal local minima, thereby delaying discovery of the global minimum. In this paper, a globally-biased simplicial partition Disimpl algorithm for global optimization of expensive Lipschitz continuous functions with an unknown Lipschitz constant is proposed. A scheme for an adaptive balancing of local and global information during the search is introduced, implemented, experimentally investigated, and compared with the well-known Direct and Direct l methods. Extensive numerical experiments executed on 800 multidimensional multiextremal test functions show a promising performance of the new acceleration technique with respect to competitors.     

The classic differential evolution algorithm and its convergence properties

Differential evolution algorithms represent an up to date and efficient way of solving complicated optimization tasks. In this article we concentrate on the ability of the differential evolution algorithms to attain the global minimum of the cost function. We demonstrate that although often declared as a global optimizer the classic differential evolution algorithm does not in general guarantee the convergence to the global minimum. To improve this weakness we design a simple modification of the classic differential evolution algorithm. This modification limits the possible premature convergence to local minima and ensures the asymptotic global convergence. We also introduce concepts that are necessary for the subsequent proof of the asymptotic global convergence of the modified algorithm. We test the classic and modified algorithm by numerical experiments and compare the efficiency of finding the global minimum for both algorithms. The tests confirm that the modified algorithm is significantly more efficient with respect to the global convergence than the classic algorithm.     

A global minimization algorithm for a class of one-dimensional functions

An algorithm is developed for finding the global minimum of a continuously differentiable function on a compact interval in R₁. The function is assumed to be the sum of a convex and a concave function, each of which belongs to C¹[a, b]. Any one-dimensional function with a bounded second derivative can be so written and, therefore, such functions generally have many local minima. The algorithm utilizes the structure of the objective to produce an ?-optimal solution by a sequence of simple one-dimensional convex programs.     

An analysis of neighborhood functions on generic solution spaces

The effectiveness of local search algorithms on discrete optimization problems is influenced by the choice of the neighborhood function. A neighborhood function that results in all local minima being global minima is said to have zero L-locals. A polynomially sized neighborhood function with zero L-locals would ensure that at each iteration, a local search algorithm would be able to find an improving solution or conclude that the current solution is a global minimum. This paper presents a recursive relationship for computing the number of neighborhood functions over a generic solution space that results in zero L-locals. Expressions are also given for the number of tree neighborhood functions with zero L-locals. These results provide a first step towards developing expressions that are applicable to discrete optimization problems, as well as providing results that add to the collection of solved graphical enumeration problems.     

Global minimum test problem construction

A method is presented for the construction of test problems for which the global minimum point is known.Given a bounded convex polyhedron inR ⁿ , and a selected vertex, a concave quadratic function is constructed which attains its global minimum at the selected vertex. In general, this function will also have many other local minima.This research was supported in part by NSF Grant MCS 81-01214.     

Local Optimization Method with Global Multidimensional Search

This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present results of numerical experiments with well-known test problems and with the so-called cluster function. These results confirm that the proposed algorithms allows one to find a global minimizer or at least a deep local minimizer of a function with a huge amount of shallow local minima.     

Test Problem Generator by Neural Network for Algorithms that Try Solving Nonlinear Programming Problems Globally

A test problem generator, by means of neural networks nonlinear function approximation capability, is given in this paper which provides test problems, with many predetermined local minima and a global minimum, to evaluate nonlinear programming algorithms that are designed to solve the problem globally.     

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.     

Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

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 locating all roots of systems of nonlinear equations inside bounded domain using global optimization methods

A novel method of locating all real roots of systems of nonlinear equations is presented here. The root finding problem is transformed to optimization problem, enabling the application of global optimization methods. Among many methods that exist in global optimization literature, Multistart and Minfinder are applied here because of their ability to locate not only the global minimum but also all local minima of the objective function. This procedure enables to locate all the possible roots of the system. Various test cases have been examined in order to validate the proposed procedure. This methodology does not make use of a priori knowledge of the number of the existing roots in the same manner as the corresponding global optimization methodology which does not make use of a priori knowledge of the existed number of local minima. Application of the new methodology resulted in finding all the roots in all test cases. The proposed methodology is general enough to be applied in any root finding problem.     

A Hybrid Descent Method for Global Optimization

In this paper, a hybrid descent method, consisting of a simulated annealing algorithm and a gradient-based method, is proposed. The simulated annealing algorithm is used to locate descent points for previously converged local minima. The combined method has the descent property and the convergence is monotonic. To demonstrate the effectiveness of the proposed hybrid descent method, several multi-dimensional non-convex optimization problems are solved. Numerical examples show that global minimum can be sought via this hybrid descent method.