Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

On some characterizations of preinvex fuzzy mappings

Jeyakumar (Methods Oper. Res. 55:109–125, 1985) and Weir and Mond (J. Math. Anal. Appl. 136:29–38, 1988) introduced the concept of preinvex function. The preinvex functions have some interesting properties. For example, every local minimum of a preinvex function is a global minimum and nonnegative linear combinations of preinvex functions are preinvex. Invex functions were introduced by Hanson (J. Math. Anal. Appl. 80:545–550, 1981) as a generalization of differentiable convex functions. These functions are more general than the convex and pseudo convex ones. The type of invex function is equivalent to the type of function whose stationary points are global minima. Under some conditions, an invex function is also a preinvex function. Syau (Fuzzy Sets Syst. 115:455–461, 2000) introduced the concepts of pseudoconvexity, invexity, and pseudoinvexity for fuzzy mappings of one variable by using the notion of differentiability and the results proposed by Goestschel and Voxman (Fuzzy Sets Syst. 18:31–43, 1986). Wu and Xu (Fuzzy Sets Syst 159:2090–2103, 2008) introduced the concepts of fuzzy pseudoconvex, fuzzy invex, fuzzy pseudoinvex, and fuzzy preinvex mapping from \(\mathbb{R}^{n}\) to the set of fuzzy numbers based on the concept of differentiability of fuzzy mapping defined by Wang and Wu (Fuzzy Sets Syst. 138:559–591, 2003). In this paper, we present some characterizations of preinvex fuzzy mappings. The necessary and sufficient conditions for differentiable and twice differentiable preinvex fuzzy mapping are provided. These characterizations correct and improve previous results given by other authors. This fact is shown with examples. Moreover, we introduce additional conditions under which these results are valid.     

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.     

Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems

This paper examines the influence of two major aspects on the solution quality of surrogate model algorithms for computationally expensive black-box global optimization problems, namely the surrogate model choice and the method of iteratively selecting sample points. A random sampling strategy (algorithm SO-M-c) and a strategy where the minimum point of the response surface is used as new sample point (algorithm SO-M-s) are compared in numerical experiments. Various surrogate models and their combinations have been used within the SO-M-c and SO-M-s sampling frameworks. The Dempster–Shafer Theory approach used in the algorithm by Müller and Piché (J Glob Optim 51:79–104, 2011) has been used for combining the surrogate models. The algorithms are numerically compared on 13 deterministic literature test problems with 2–30 dimensions, an application problem that deals with groundwater bioremediation, and an application that arises in energy generation using tethered kites. NOMAD and the particle swarm pattern search algorithm (PSWARM), which are derivative-free optimization methods, have been included in the comparison. The algorithms have also been compared to a kriging method that uses the expected improvement as sampling strategy (FEI), which is similar to the Efficient Global Optimization (EGO) algorithm. Data and performance profiles show that surrogate model combinations containing the cubic radial basis function (RBF) model work best regardless of the sampling strategy, whereas using only a polynomial regression model should be avoided. Kriging and combinations including kriging perform in general worse than when RBF models are used. NOMAD, PSWARM, and FEI perform for most problems worse than SO-M-s and SO-M-c. Within the scope of this study a Matlab toolbox has been developed that allows the user to choose, among others, between various sampling strategies and surrogate models and their combinations. The open source toolbox is available from the authors upon request.     

On Galois cohomology of semisimple groups over local and global fields of positive characteristic, II

We show that the recent results of Prasad and Rapinchuk (Adv. Math. 207(2), 646–660, 2006) on the existence and uniqueness of certain global forms of semisimple algebraic groups with given local behaviour in the case of number fields still hold in the case of global function fields.     

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.     

A global optimization algorithm using adaptive random search

A new random-search global optimization is described in which the variance of the step-size distribution is periodically optimized. By searching over a variance range of 8 to 10 decades, the algorithm finds the step-size distribution that yields the best local improvement in the criterion function. The variance search is then followed by a specified number of iterations of local random search where the step-size variance remains fixed. Periodic wide-range searches are introduced to ensure that the process does not stop at a local minimum. The sensitivity of the complete algorithm to various search parameters is investigated experimentally for a specific test problem. The ability of the method to locate global minima is illustrated by an example. The method also displays considerable problem independence, as demonstrated by two large and realistic example problems: (1) the identification of 25 parameters in a nonlinear model of a five-degrees-of-freedom mechanical dynamic system and (2) solution of a 24-parameter inverse problem required to identify a pulse train whose frequency spectrum matched a desired reference spectrum.     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

Application of Deterministic Low-Discrepancy Sequences in Global Optimization

It has been recognized through theory and practice that uniformly distributed deterministic sequences provide more accurate results than purely random sequences. A quasi Monte Carlo (QMC) variant of a multi level single linkage (MLSL) algorithm for global optimization is compared with an original stochastic MLSL algorithm for a number of test problems of various complexities. An emphasis is made on high dimensional problems. Two different low-discrepancy sequences (LDS) are used and their efficiency is analysed. It is shown that application of LDS can significantly increase the efficiency of MLSL. The dependence of the sample size required for locating global minima on the number of variables is examined. It is found that higher confidence in the obtained solution and possibly a reduction in the computational time can be achieved by the increase of the total sample size N. N should also be increased as the dimensionality of problems grows. For high dimensional problems clustering methods become inefficient. For such problems a multistart method can be more computationally expedient.     

Test Functions with Variable Attraction Regions for Global Optimization Problems

Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima.     

A successive descent algorithm over a system of local minima

A successive descent algorithm over a system of local minima has been developed to find the global minimum of a function of many variables defined on a simply connected compact set. If the number of local minima is finite and a bound on the global minimum is given, the algorithm finds the global minimum in finitely many steps. Test examples are presented. Translated from Prikladnaya Matematika i Informatika, No. 30, pp. 46–54, 2008.     

Stochastic global optimization methods part II: Multi level methods

In Part II of our paper, two stochastic methods for global optimization are described that, with probability 1, find all relevant local minima of the objective function with the smallest possible number of local searches. The computational performance of these methods is examined both analytically and empirically.     

Algebraic Hecke characters and strictly compatible systems of abelian mod p Galois representations over global fields

In [10] (C R Acad Sci Paris Ser I Math 323(2) 117–120, 1996), [11] (Math Res Lett 10(1):71–83 2003), [12] (Can J Math 57(6):1215–1223 2005), Khare showed that any strictly compatible systems of semisimple abelian mod p Galois representations of a number field arises from a unique finite set of algebraic Hecke characters. In this article, we consider a similar problem for arbitrary global fields. We give a definition of Hecke character which in the function field setting is more general than previous definitions by Goss and Gross and define a corresponding notion of compatible system of mod p Galois representations. In this context we present a unified proof of the analog of Khare’s result for arbitrary global fields. In a sequel we shall apply this result to strictly compatible systems arising from Drinfeld modular forms, and thereby attach Hecke characters to cuspidal Drinfeld Hecke eigenforms.     

Optimal Transport, Convection, Magnetic Relaxation and Generalized Boussinesq Equations

We establish a connection between optimal transport theory (see Villani in Topics in optimal transportation. Graduate studies in mathematics, vol. 58, AMS, Providence, 2003, for instance) and classical convection theory for geophysical flows (Pedlosky, in Geophysical fluid dynamics, Springer, New York, 1979). Our starting point is the model designed few years ago by Angenent, Haker, and Tannenbaum (SIAM J. Math. Anal. 35:61–97, 2003) to solve some optimal transport problems. This model can be seen as a generalization of the Darcy–Boussinesq equations, which is a degenerate version of the Navier–Stokes–Boussinesq (NSB) equations. In a unified framework, we relate different variants of the NSB equations (in particular what we call the generalized hydrostatic-Boussinesq equations) to various models involving optimal transport (and the related Monge–Ampère equation, Brenier in Commun. Pure Appl. Math. 64:375–417, 1991; Caffarelli in Commun. Pure Appl. Math. 45:1141–1151, 1992). This includes the 2D semi-geostrophic equations (Hoskins in Annual review of fluid mechanics, vol. 14, pp. 131–151, Palo Alto, 1982; Cullen et al. in SIAM J. Appl. Math. 51:20–31, 1991, Arch. Ration. Mech. Anal. 185:341–363, 2007; Benamou and Brenier in SIAM J. Appl. Math. 58:1450–1461, 1998; Loeper in SIAM J. Math. Anal. 38:795–823, 2006) and some fully nonlinear versions of the so-called high-field limit of the Vlasov–Poisson system (Nieto et al. in Arch. Ration. Mech. Anal. 158:29–59, 2001) and of the Keller–Segel for Chemotaxis (Keller and Segel in J. Theor. Biol. 30:225–234, 1971; Jäger and Luckhaus in Trans. Am. Math. Soc. 329:819–824, 1992; Chalub et al. in Mon. Math. 142:123–141, 2004). Mathematically speaking, we establish some existence theorems for local smooth, global smooth or global weak solutions of the different models. We also justify that the inertia terms can be rigorously neglected under appropriate scaling assumptions in the generalized Navier–Stokes–Boussinesq equations. Finally, we show how a “stringy” generalization of the AHT model can be related to the magnetic relaxation model studied by Arnold and Moffatt to obtain stationary solutions of the Euler equations with prescribed topology (see Arnold and Khesin in Topological methods in hydrodynamics. Applied mathematical sciences, vol. 125, Springer, Berlin, 1998; Moffatt in J. Fluid Mech. 159:359–378, 1985, Topological aspects of the dynamics of fluids and plasmas. NATO adv. sci. inst. ser. E, appl. sci., vol. 218, Kluwer, Dordrecht, 1992; Schonbek in Theory of the Navier–Stokes equations, Ser. adv. math. appl. sci., vol. 47, pp. 179–184, World Sci., Singapore, 1998; Vladimirov et al. in J. Fluid Mech. 390:127–150, 1999; Nishiyama in Bull. Inst. Math. Acad. Sin. (N.S.) 2:139–154, 2007).     

Counterexamples to a triality theorem for quadratic-exponential minimization problems

The main goal of this note is to give a counterexample to the Triality Theorem in Gao and Ruan (Math Methods Oper Res 67:479–491, 2008). This is done first by considering a more general optimization problem with the aim to encompass several examples from Gao and Ruan (Math Methods Oper Res 67:479–491, 2008) and other papers by Gao and his collaborators (see f.i. Gao Duality principles in nonconvex systems. Theory, methods and applications. Kluwer, Dordrecht, 2000; Gao and Sherali Advances in applied mathematics and global optimization. Springer, Berlin, 2009). We perform a thorough analysis of the general optimization problem in terms of local extrema while presenting several counterexamples.     

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.     

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.     

Lattices of minimum covolume are non-uniform

In this article, we prove that a lattice of minimum covolume in a simple Lie group over a local field of positive characteristic is non-uniform if the Weil’s conjecture on Tamagawa numbers [Wei61] holds. This, in part, answers Lubotzky’s conjecture [Lub91].     

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.     

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.