Computational comparison of two methods for constrained global optimization

For constrained concave global minimization problems, two very different solution techniques have been investigated. The first such method is a stochastic mulitstart approach which typically finds, with high probability, all local minima for the problem. The second method is deterministic and guarantees a global minimum solution to within any user specified tolerance. It is the purpose of this paper to make a careful comparison of these two methods on a range of test problems using separable concave objectives over compact polyhedral sets, and to investigate in this way the advantages and disadvantages of each method. A direct computational comparison, on the same set of over 140 problems, is presented.     

Global optimization and stochastic differential equations

Let ⁿ be then-dimensional real Euclidean space,x=(x ₁,x ₂, ...,x _n)^{T n} , and letf: ⁿ R be a real-valued function. We consider the problem of finding the global minimizers off. A new method to compute numerically the global minimizers by following the paths of a system of stochastic differential equations is proposed. This method is motivated by quantum mechanics. Some numerical experience on a set of test problems is presented. The method compares favorably with other existing methods for global optimization.This research has been supported by the European Research Office of the US Army under Contract No. DAJA-37-81-C-0740.The third author gratefully acknowledges Prof. A. Rinnooy Kan for bringing to his attention Ref. 4.     

Enhancing PSO methods for global optimization

The Particle Swarm Optimization (PSO) method is a well-established technique for global optimization. During the past years several variations of the original PSO have been proposed in the relevant literature. Because of the increasing necessity in global optimization methods in almost all fields of science there is a great demand for efficient and fast implementations of relative algorithms. In this work we propose three modifications of the original PSO method in order to increase the speed and its efficiency that can be applied independently in almost every PSO variant. These modifications are: (a) a new stopping rule, (b) a similarity check and (c) a conditional application of some local search method. The proposed were tested using three popular PSO variants and a variety test functions. We have found that the application of these modifications resulted in significant gain in speed and efficiency.     

Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization

This paper presents some simple technical conditions that guarantee the convergence of a general class of adaptive stochastic global optimization algorithms. By imposing some conditions on the probability distributions that generate the iterates, these stochastic algorithms can be shown to converge to the global optimum in a probabilistic sense. These results also apply to global optimization algorithms that combine local and global stochastic search strategies and also those algorithms that combine deterministic and stochastic search strategies. This makes the results applicable to a wide range of global optimization algorithms that are useful in practice. Moreover, this paper provides convergence conditions involving the conditional densities of the random vector iterates that are easy to verify in practice. It also provides some convergence conditions in the special case when the iterates are generated by elliptical distributions such as the multivariate Normal and Cauchy distributions. These results are then used to prove the convergence of some practical stochastic global optimization algorithms, including an evolutionary programming algorithm. In addition, this paper introduces the notion of a stochastic algorithm being probabilistically dense in the domain of the function and shows that, under simple assumptions, this is equivalent to seeing any point in the domain with probability 1. This, in turn, is equivalent to almost sure convergence to the global minimum. Finally, some simple results on convergence rates are also proved.     

Parallel methods for verified global optimization practice and theory

We present a new parallel method for verified global optimization, using a centralized mediator for the dynamic load balancing. The new approach combines the advantages of two previous models, the master slave model and the processor farm. Numerical results show the efficiency of this new method. For a large number of problems at least linear speedup is reached. The efficiency of this new method is also confirmed by a comparison with other parallel methods for verified global optimization. A theoretical study proves that using the best-first strategy to choose the next box for subdivision, no real superlinear speedup may be expected concerning the number of iterations. Moreover, the potential of parallelization of methods of verified global optimization is discussed in general.     

SPT: a stochastic tunneling algorithm for global optimization

A stochastic approach to solving unconstrained continuous-function global optimization problems is presented. It builds on the tunneling approach to deterministic optimization presented by Barhen and co-workers (Bahren and Protopopescu, in: State of the Art in Global Optimization, Kluwer, 1996; Barhen et al., Floudas and Pardalos (eds.), TRUST: a deterministic algorithm for global optimization, 1997) by combining a series of local descents with stochastic searches. The method uses a rejection-based stochastic procedure to locate new local minima descent regions and a fixed Lipschitz-like constant to reject unpromising regions in the search space, thereby increasing the efficiency of the tunneling process. The algorithm is easily implemented in low-dimensional problems and scales easily to large problems. It is less effective without further heuristics in these latter cases, however. Several improvements to the basic algorithm which make use of approximate estimates of the algorithms parameters for implementation in high-dimensional problems are also discussed. Benchmark results are presented, which show that the algorithm is competitive with the best previously reported global optimization techniques. A successful application of the approach to a large-scale seismology problem of substantial computational complexity using a low-dimensional approximation scheme is also reported.     

Parallel algorithms for global optimization

In this paper, we report results of implementations of algorithms designed (i) to solve the global optimization problem (GOP) and (ii) to run on a parallel network of transputers. There have always been two alternative approaches to the solution of the GOP, probabilistic and deterministic. Interval methods can be implemented on our network of transputers using Concurrent ADA, and a secondary objective of the tests reported was to investigate the relative computer times required by parallel interval algorithms compared to probabilistic methods.     

Topographical global optimization using pre-sampled points

A method for global minimization of a functionf(x), x A R ⁿ by using presampled global points inA is presented. The global points are obtained by uniform sampling, discarding points too near an already accepted point to obtain a very uniform covering. The accepted points and their nearest-neighbours matrix are stored on a file. When optimzing a given function these pre-sampled points and the matrix are read from file. Then the function value of each point is computed and itsk nearest neighbours that have larger function values are marked. The points for which all its neighbours are marked are extracted as promising starting points for local minimizations. Results from a parallel implementation are presented. The working of a sequential version in Fortran is illustrated.     

Internal modelling of objective functions for global optimization

Global optimization requires an adequate internal representation of the objective function for success in a reasonable number of function evaluations. A method for determining the location of a new function evaluation, based on a representation using a stationary stochastic process model, is investigated and some results are given.     

Stochastic global optimization methods part I: Clustering methods

In this stochastic approach to global optimization, clustering techniques are applied to identify local minima of a real valued objective function that are potentially global. Three different methods of this type are described; their accuracy and efficiency are analyzed in detail.     

An adaptive stochastic global optimization algorithm for one-dimensional functions

In this paper a new algorithm is proposed, based upon the idea of modeling the objective function of a global optimization problem as a sample path from a Wiener process. Unlike previous work in this field, in the proposed model the parameter of the Wiener process is considered as a random variable whose conditional (posterior) distribution function is updated on-line. Stopping criteria for Bayesian algorithms are discussed and detailed proofs on finite-time stopping are provided.This research has been partially supported by Progetto MURST 40% Metodi di Ottimizzazione per le Decisioni.     

Nonautonomous stochastic search for global minimum in continuous optimization

Various iterative stochastic optimization schemes can be represented as discrete-time Markov processes defined by the nonautonomous equation _Xt+1=_Tt(_Xt,_Yt)$X_{t+1}=T_t(X_t,Y_t)$, where _Yt$Y_t$ is an independent sequence and _Tt$T_t$ is a sequence of mappings. This paper presents a general framework for the study of the stability and convergence of such optimization processes. Some applications are given: the mathematical convergence analysis of two optimization methods, the elitist evolution strategy (μ+λ)$(\mu +\lambda )$ and the grenade explosion method, is presented.     

A review of statistical models for global optimization

A review of statistical models for global optimization is presented. Rationality of the search for a global minimum is formulated axiomatically and the features of the corresponding algorithm are derived from the axioms. Furthermore the results of some applications of the proposed algorithm are presented and the perspectives of the approach are discussed.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

Unified theory of augmented Lagrangian methods for constrained global optimization

We classify in this paper different augmented Lagrangian functions into three unified classes. Based on two unified formulations, we construct, respectively, two convergent augmented Lagrangian methods that do not require the global solvability of the Lagrangian relaxation and whose global convergence properties do not require the boundedness of the multiplier sequence and any constraint qualification. In particular, when the sequence of iteration points does not converge, we give a sufficient and necessary condition for the convergence of the objective value of the iteration points. We further derive two multiplier algorithms which require the same convergence condition and possess the same properties as the proposed convergent augmented Lagrangian methods. The existence of a global saddle point is crucial to guarantee the success of a dual search. We generalize in the second half of this paper the existence theorems for a global saddle point in the literature under the framework of the unified classes of augmented Lagrangian functions.     

Accelerations for global optimization covering methods using second derivatives

Two improvements for the algorithm of Breiman and Cutler are presented. Better envelopes can be built up using positive quadratic forms. Better utilization of first and second derivative information is attained by combining both global aspects of curvature and local aspects near the global optimum. The basis of the results is the geometric viewpoint developed by the first author and can be applied to a number of covering type methods. Improvements in convergence rates are demonstrated empirically on standard test functions.Partially supported by an University of Canterbury Erskine grant.     

Bayesian stopping rules for multistart global optimization methods

By far the most efficient methods for global optimization are based on starting a local optimization routine from an appropriate subset of uniformly distributed starting points. As the number of local optima is frequently unknown in advance, it is a crucial problem when to stop the sequence of sampling and searching. By viewing a set of observed minima as a sample from a generalized multinomial distribution whose cells correspond to the local optima of the objective function, we obtain the posterior distribution of the number of local optima and of the relative size of their regions of attraction. This information is used to construct sequential Bayesian stopping rules which find the optimal trade off between reliability and computational effort.     

New interval methods for constrained global optimization

Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for being used in inequality constrained global optimization problems. The usefulness of these new techniques is shown by computational studies.