On a new stochastic global optimization algorithm based on censored observations

In this paper a new algorithm is proposed for global optimization problems. The main idea is that of modifying a standard clustering approach by sequentially sampling the objective function while adaptively deciding an appropriate sample size. Theoretical as well as computational results are presented.     

Sequential stopping rules for the multistart algorithm in global optimisation

In this paper a sequential stopping rule is developed for the Multistart algorithm. A statistical model for the values of the observed local maxima of an objective function is introduced in the framework of Bayesian non-parametric statistics. A suitablea-priori distribution is proposed which is general enough and which leads to computationally manageable expressions for thea-posteriori distribution. Sequential stopping rules of thek-step look-ahead kind are then explicitly derived, and their numerical effectiveness compared.     

Towards “Ideal Multistart”. A stochastic approach for locating the minima of a continuous function inside a bounded domain

A stochastic global optimization method based on Multistart is presented. In this, the local search is conditionally applied with a probability that takes in account the topology of the objective function at the detail offered by the current status of exploration. As a result, the number of unnecessary local searches is drastically limited, yielding an efficient method. Results of its application on a set of common test functions are reported, along with a performance comparison against other established methods of similar nature.     

Docking of Atomic Clusters Through Nonlinear Optimization

The problem of molecular docking is defined as that of finding a minimum energy configuration of a pair of molecular structures (usually consisting of proteins, DNA or RNA fragments). It is often assumed that the two interacting structures can be considered as rigid bodies and that it is of interest to researchers to develop methods which enable to discover the potential binding sites. Many different models have been proposed in the literature for the definition of the potential energy between two molecular structures, most of which contain at least a term (known as Van Der Waals interaction) which accounts for pairwise attraction between atoms, a repulsion term and a term which takes into account electrostatic forces (Coulomb interaction). Some well known models, and in particular those used in rigid docking, are based on the assumption that the only terms which are relevant in the process of docking are pairwise interactions between atoms belonging to the two different parts of the structure. In this paper the problem of finding the lowest energy configuration of a pair of biomolecular structures, considered as rigid bodies, is defined and formulated as a global optimization problem. In terms of dimension of the search space this formulation is not 'high-dimensional', as there are only six degrees of freedom: 3 translation and 3 rotation parameters. However the energy surface of the docking problem is characterized by a huge number of local minima; moreover each function evaluation is quite expensive (interesting structures usually possess a few thousand atoms each). So there is a strong need both of local and of global optimization procedures. In this paper a local optimization technique, based upon standard non linear programming software and a penalized objective function, is introduced and its potential usefulness in the context of global optimization is outlined.     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.     

Stopping eules for the multistart method when different local minima have different function values

In this paper the Bayesian stopping rules derived by Boendeb and Rin-Nooy Kan for the Multistart method in global optimization are adjusted to incorporate both in the likelihood and in the loss function the a priori assumption that different local minimum points have different, function values.     

Relaxing the Assumptions of the Multilevel Single Linkage Algorithm

In this paper we relax the assumptions of a well known algorithm for continuous global optimization, Multilevel Single Linkage (MLSL). It is shown that the good theoretical properties of MLSL are shared by a slightly different algorithm, Non-monotonic MLSL (NM MLSL), but under weaker assumptions. The main difference with MLSL is the fact that in NM MLSL some non-monotonic sequences of sampled points are also considered in order to decide whether to start or not a local search, while MLSL only considers monotonic decreasing sequences. The modification is inspired by non-monotonic methods for local searches. This revised version was published online in July 2006 with corrections to the Cover Date.     

Combining a Local Search and Grover’s Algorithm in Black-Box Global Optimization

Grover’s quantum algorithm promises a quadratic acceleration for any problem formulable as a search. For unstructured search problems, its implementation and performance are well understood. The curse of dimensionality and the intractability of the general global optimization problem require any identifiable structure or regularity to be incorporated into a solution method. This paper addresses the application of Grover’s algorithm when a local search technique is available, thereby combining the quadratic acceleration with the acceleration seen in the multistart method. The author thanks Dr. Bill Baritompa for helpful discussions.     

A Note on the Griewank Test Function

In this paper we analyze a widely employed test function for global optimization, the Griewank function. While this function has an exponentially increasing number of local minima as its dimension increases, it turns out that a simple Multistart algorithm is able to detect its global minimum more and more easily as the dimension increases. A justification of this counterintuitive behavior is given. Some modifications of the Griewank function are also proposed in order to make it challenging also for large dimensions.     

Solving molecular distance geometry problems by global optimization algorithms

In this paper we consider global optimization algorithms based on multiple local searches for the Molecular Distance Geometry Problem (MDGP). Three distinct approaches (Multistart, Monotonic Basin Hopping, Population Basin Hopping) are presented and for each of them a computational analysis is performed. The results are also compared with those of two other approaches in the literature, the DGSOL approach (Moré, Wu in J. Glob. Optim. 15:219–234, 1999) and a SDP based approach (Biswas et al. in An SDP based approach for anchor-free 3D graph realization, Technical Report, Operations Research, Stanford University, 2005).