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.     

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.     

On the Definition of a Minimum in Parameter Optimization

For the unconstrained minimization of an ordinary function, there are essentially two definitions of a minimum. The first involves the inequality \(\le \), and the second, the inequality <. The purpose of this Forum is to discuss the consequences of using these definitions for finding local and global minima of the constant objective function. The first definition says that every point on the constant function is a local minimum and maximum, as well as a global minimum and maximum. This is not a rational result. On the other hand, the second definition says that the constant function cannot be minimized in an unconstrained problem. It must be treated as a constrained problem where the constant function is the lower boundary of the feasible region. This is a rational result. As a consequence, it is recommended that the standard definition (\(\le \)) for a minimum be replaced by the second definition (<).     

Random tunneling by means of acceptance-rejection sampling for global optimization

Any global minimization algorithm is made by several local searches performed sequentially. In the classical multistart algorithm, the starting point for each new local search is selected at random uniformly in the region of interest. In the tunneling algorithm, such a starting point is required to have the same function value obtained by the last local minimization. We introduce the class of acceptance-rejection based algorithms in order to investigate intermediate procedures. A particular instance is to choose at random the new point approximately according to a Boltzmann distribution, whose temperatureT is updated during the algorithm. AsT 0, such distribution peaks around the global minima of the cost function, producing a kind of random tunneling effect. The motivation for such an approach comes from recent works on the simulated annealing approach in global optimization. The resulting algorithm has been tested on several examples proposed in the literature.     

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 role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

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 minimization algorithm for Lipschitz functions

The global optimization problem with and f(x) satisfying the Lipschitz condition , is considered. To solve it a region-search algorithm is introduced. This combines a local minimum algorithm with a procedure that at the ith iteration finds a region S _i where the global minimum has to be searched for. Specifically, by making use of the Lipschitz condition, S _i , which is a sequence of intervals, is constructed by leaving out from S _i-1 an interval where the global minimum cannot be located. A convergence property of the algorithm is given. Further, the ratio between the measure of the initial feasible region and that of the unexplored region may be used as stop rule. Numerical experiments are carried out; these show that the algorithm works well in finding and reducing the measure of the unexplored region.     

A Crystal Growth Approach for Topographical Global Optimization

A new approach for topographical global minimization of a function f(x), x A Rⁿ by using sampled points in A is presented. The globally sampled points are firstly obtained by uniform random sampling or uniform sampling with threshold distances. The point with the lowest function value is used as the nucleus atom to start a crystal growth process. A first triangular nucleus includes the nucleus atom and two nearest points. Sequential crystal growth is continued for which a point next closest to the nucleus atom is bonded to the crystal by attaching to two nearest solidified points. A solidified point will be marked during the crystal growth process if any of two connected points has a lower function value. Upon completion of entire crystal growth process, all unmarked points are then used as starting points for subsequent local minimizations. Extension of the topographical algorithms to constrained problems is exercised by using penalty functions. Formulas for estimation on the number of sampled points for problems with an assumed number of local minima are provided. Results on three global minimization problems by two topographical algorithms are discussed.     

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.     

Maximization of the Ratio of Two Convex Quadratic Functions over a Polytope

In this paper, we will develop an algorithm for solving a quadratic fractional programming problem which was recently introduced by Lo and MacKinlay to construct a maximal predictability portfolio, a new approach in portfolio analysis. The objective function of this problem is defined by the ratio of two convex quadratic functions, which is a typical global optimization problem with multiple local optima. We will show that a well-designed branch-and-bound algorithm using (i) Dinkelbach's parametric strategy, (ii) linear overestimating function and (iii) -subdivision strategy can solve problems of practical size in an efficient way. This algorithm is particularly efficient for Lo-MacKinlay's problem where the associated nonconvex quadratic programming problem has low rank nonconcave property.     

Finding all solutions of nonlinearly constrained systems of equations

A new approach is proposed for finding all-feasible solutions for certain classes of nonlinearly constrained systems of equations. By introducing slack variables, the initial problem is transformed into a global optimization problem (P) whose multiple global minimum solutions with a zero objective value (if any) correspond to all solutions of the initial constrained system of equalities. All-globally optimal points of (P) are then localized within a set of arbitrarily small disjoint rectangles. This is based on a branch and bound type global optimization algorithm which attains finite-convergence to each of the multiple global minima of (P) through the successive refinement of a convex relaxation of the feasible region and the subsequent solution of a series of nonlinear convex optimization problems. Based on the form of the participating functions, a number of techniques for constructing this convex relaxation are proposed. By taking advantage of the properties of products of univariate functions, customized convex lower bounding functions are introduced for a large number of expressions that are or can be transformed into products of univariate functions. Alternative convex relaxation procedures involve either the difference of two convex functions employed in BB [23] or the exponential variable transformation based underestimators employed for generalized geometric programming problems [24]. The proposed approach is illustrated with several test problems. For some of these problems additional solutions are identified that existing methods failed to locate.     

On the Convergence of Inhomogeneous Markov Chains Approximating Equilibrium Placements of Flexible Objects

This paper deals with the minimization of local forces in two-dimensional placements of flexible objects within rigid boundaries. The objects are disks of the same size but, in general, of different materials. Potential applications include the design of new amorphous polymeric and related granular materials as well as the design of package cushioning systems. The problem is considered on a grid structure with a fixed step size w and for a fixed diameter of the discs, i.e., the number of placed disks may increase as the size of the placement region increases. The near-equilibrium configurations have to be calculated from uniformly distributed random initial placements. The final arrangements of disks must ensure that any particular object is deformed only within the limits of elasticity of the material. The main result concerns -approximations of the probability distribution on the set of equilibrium placements. Under a natural assumption about the configuration space, we prove that a run-time of n+log^O(1)(1/} is sufficient to approach with probability 1 – the minimum value of the objective function, where depends on the maximum of the escape depth of local minima within the underlying energy landscape. The result is derived from a careful analysis of the interaction among probabilities assigned to configurations from adjacent distance levels to minimum placements. The overall approach for estimating the convergence rate is relatively independent of the particular placement problem and can be applied to various optimization problems with similar properties of the associated landscape of the objective function.     

Global Optimization: On Pathlengths in Min-Max Graphs

Let f be a smooth nondegenerate real valued function on a finite dimensional, compact and connected Riemannian manifold. The bipartite min-max graph is defined as follows. Its nodes are formed by the set of local minima and the set of local maxima. Two nodes (a local minimum and a local maximum) are connected in by means of an edge if some trajectory of the corresponding gradient flow connects them. Given a natural number k, we construct a function f such that the length of the shortest path in between two specific local minima exceeds k. The latter construction is independent of the underlying Riemannian metric.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

On global minima of semistrictly quasiconcave functions

This paper studies the global behaviour of semistrictly quasiconcave functions with (possibly) nonconvex domain in the presence of global minima. We mainly present necessary conditions for the existence of global minima of a semistrictly quasiconcave real-valued function f with domain , and we show how the geometric structure of its graph and the cardinality of its range depend on the location of global minimum points. Our main result states that if a global minimum of f is achieved in the algebraic interior of K, then f can attain at the most n + 1 distinct function values, and the graph of f has a simple structure determined by a sequence of nested affine subspaces such that, essentially, f is constant on the set difference of each pair of successive affine subspaces.     

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.     

Verallgemeinerungen eines Satzes von H. Steinhaus

The following result is due to H. Steinhaus [20]: “If A,B?R are sets of positive inner Lebesgue measure and if the function f: R x R→R is defined by f(x,y):=x+y (x,y?R), then the interior of f(A x B) is non void”. In this note there is proved, that the theorem of H. Steinhaus remains valid, if

1. R is replaced by certain topological measure spaces X, Y and a Hausdorff space Z,
2. f is a continuous function from an open set T?X x Y into Z and satisfies a special local (respectively global) solvability condition in T,
3. A?X is a set of positive outer measure, B?Y contains a set of positive measure and A x B?T.

     

γ-Subdifferential and γ-convexity of functions on the real line

In this paper the -subdifferential and -convexity of real-valued functions on the real line are introduced. By means of the -subdifferential, a new necessary condition for global minima (or maxima) is formulated which many local minima (or maxima) cannot satisfy. The -convexity is used to state sufficient conditions for global minima. The class of -convex functions is relatively large. For example, there are -convex functions which are not continuous anywhere. Nevertheless, a -local minimum of a -convex function is always a global minimum. Furthermore, if a -convex function attains its global minimum, then it does so near the boundary of its domain.This research was supported by the Alexander von Humboldt Foundation.     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.