Bayesian testing of nonparametric hypotheses and its application to global optimization

Random distribution functions are the basic tool for solving nonparametric decision-theoretic problems. In 1974, Doksum introduced the family of distributions neutral to the right, that is, distributions such thatF(t ₁),[F(t ₂)–F(t ₁)]/[1 –F(t ₁)],...,[F(t _k)–F(t _{k – 1})]/[1 –F(t _{k – 1})] are independent whenevert ₁ < ... <t _kIn practice, application of distributions neutral to the right has been prevented by the lack of a manageable analytical expression for probabilities of the typeP(F(t)<q) for fixedt andq. A subclass of such distributions can be provided which allows for a close expression of the characteristic function of log[1–F(t)], given the sample. Then, thea posteriori distribution ofF(t) is obtained by numerical evaluation of a Fourier integral. As an application, the global optimization problem is formulated as a problem of inference about the quantiles of the distributionF(y) of the random variableY=f(X), wheref is the objective function andX is a random point in the search domain.The author thanks J. Koronacki and R. Zielinski of the Polish Academy of Sciences for their valuable criticism during the final draft of the paper.     

Consistency of a myopic Bayesian algorithm for one-dimensional global optimization

A sequential Bayesian method for finding the maximum of a function based on myopically minimizing the expected dispersion of conditional probabilities is described. It is shown by example that an algorithm that generates a dense set of observations need not converge to the correct answer for some priors on continuous functions on the unit interval. For the Brownian motion prior the myopic algorithm is consistent; for any continuous function, the conditional probabilities converge weakly to a point mass at the true maximum.     

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.     

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.     

A survey on the global optimization problem: General theory and computational approaches

Several different approaches have been suggested for the numerical solution of the global optimization problem: space covering methods, trajectory methods, random sampling, random search and methods based on a stochastic model of the objective function are considered in this paper and their relative computational effectiveness is discussed. A closer analysis is performed of random sampling methods along with cluster analysis of sampled data and of Bayesian nonparametric stopping rules.     

Bayesian methods in global optimization

This paper reviews methods which have been proposed for solving global optimization problems in the framework of the Bayesian paradigm.     

A counterexample to a global optimization algorithm

A counterexample to an algorithm of Dien (1988) for solving a minimization problem with a quasiconcave objective function and both linear and a reverse-convex constraint shows that this algorithm needn't lead to a solution of the given problem.     

Bayesian Nonparametric Analysis for a Generalized Dirichlet Process Prior

This paper considers a generalization of the Dirichlet process which is obtained by suitably normalizing superposed independent gamma processes having increasing integer-valued scale parameter. A comprehensive treatment of this random probability measure is provided. We prove results concerning its finite-dimensional distributions, moments, predictive distributions and the distribution of its mean. Most expressions are given in terms of multiple hypergeometric functions, thus highlighting the interplay between Bayesian Nonparametrics and special functions. Finally, a suitable simulation algorithm is applied in order to compute quantities of statistical interest.     

The normal score transformation applied to a multi-univariate method of global optimization

Nonparametric global optimization methods have been developed that determine the location of their next guess based on the rank-transformed objective function evaluations rather than the actual function values themselves. Another commonly-used transformation in nonparametric statistics is the normal score transformation. This paper applies the normal score transformation to the multi-univariate method of global optimization. The benefits of the new method are shown by its performance on a standard set of global optimization test problems. The normal score transformation yields a method that gives equivalent searches for any monotonic transformation of the objective function.     

A stochastic probing algorithm for global optimization

Recently, simulated annealing methods have proven to be a valuable tool for global optimization. We propose a new stochastic method for locating the global optimum of a function. The proposed method begins with the subjective specification of a probing distribution. The objective function is evaluated at a few points sampled from this distribution, which is then updated using the collected information. The updating mechanism is based on the entropy of a move selecting distribution and is loosely connected to some notions in statistical thermodynamics. Examples of the use of the proposed method are presented. These indicate its superior performance as compared with simulated annealing. Preliminary considerations in applying the method to discrete problems are discussed.     

A dynamic clustering based differential evolution algorithm for global optimization

A dynamic clustering based differential evolution algorithm (CDE) for global optimization is proposed to improve the performance of the differential evolution (DE) algorithm. With population evolution, CDE algorithm gradually changes from exploring promising areas at the early stages to exploiting solution with high precision at the later stages. Experiments on 28 benchmark problems, including 13 high dimensional functions, show that the new method is able to find near optimal solutions efficiently. Compared with other existing algorithms, CDE improves solution accuracy with less computational effort.     

Bayesian approach to global optimization and application to multiobjective and constrained problems

In this paper, the Bayesian methods of global optimization are considered. They provide the minimal expected deviation from the global minimum. It is shown that, using the Bayesian methods, the asymptotic density of calculations of the objective function is much greater around the point of global minimum. The relation of this density to the parameters of the method and to the function is defined.Algorithms are described which apply the Bayesian methods to problems with linear and nonlinear constraints. The Bayesian approach to global multiobjective optimization is defined. Interactive procedures and reduction of multidimensional data in the case of global optimization are discussed.     

Optimal and sub-optimal stopping rules for the Multistart algorithm in global optimization

In this paper the problem of stopping the Multistart algorithm for global optimization is considered. The algorithm consists of repeatedly performing local searches from randomly generated starting points. The crucial point in this algorithmic scheme is the development of a stopping criterion; the approach analyzed in this paper consists in stopping the sequential sampling as soon as a measure of the trade-off between the cost of further local searches is greater than the expected benefit, i.e. the possibility of discovering a better optimum.Stopping rules are thoroughly investigated both from a theoretical point of view and from a computational one via extensive simulation. This latter clearly shows that the simple1-step look ahead rule may achieve surprisingly good results in terms of computational cost vs. final accuracy.The research of the second author was partially supported by Progetto MPI 40% Metodi di Ottimizzazione per le Decisioni.     

Bayesian nonparametrie inference and monte carlo optimization

As global or combinatorial optimization problems are not effectively tractable by means of deterministic techniques, Monte Carlo methods are used in practice for obtaining ”good“ approximations to the optimum. In order to test the accuracy achieved after a sample of finite size, the Bayesian nonparametric approach is proposed as a suitable context, and the theoretical as well as computational implications of prior distributions in the class of neutral to the right distributions are examined. The feasibility of the approach relatively to particular Monte Carlo procedures is finally illustrated both for the global optimization problem and the {0 - 1} programming problem.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.     

A second-order pruning step for verified global optimization

We consider pruning steps used in a branch-and-bound algorithm for verified global optimization. A first-order pruning step was given by Ratz using automatic computation of a first-order slope tuple (Ratz, Automatic Slope Computation and its Application in Nonsmooth Global Optimization. Shaker Verlag, Aachen, 1998; J. Global Optim. 14: 365–393, 1999). In this paper, we introduce a second-order pruning step which is based on automatic computation of a second-order slope tuple. We add this second-order pruning step to the algorithm of Ratz. Furthermore, we compare the new algorithm with the algorithm of Ratz by considering some test problems for verified global optimization on a floating-point computer. This paper contains some results from the author’s dissertation [29].     

Optimality condition and algorithm with deviation integral for global optimization

To study the integral global minimization, a general form of deviation integral is introduced and its properties are examined in this work. In terms of the deviation integral, optimality condition and algorithms are given. Algorithms are implemented by a properly designed Monte Carlo simulation. Numerical tests are given to show the effectiveness of the method.     

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.     

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.     

An adaptive simulated annealing algorithm for global optimization over continuous variables

A method is presented for attempting global minimization for a function of continuous variables subject to constraints. The method, calledAdaptive Simulated Annealing (ASA), is distinguished by the fact that the fixed temperature schedules and step generation routines that characterize other implementations are here replaced by heuristic-based methods that effectively eliminate the dependence of the algorithm's overall performance on user-specified control parameters. A parallelprocessing version of ASA that gives increased efficiency is presented and applied to two standard problems for illustration and comparison.This research was supported by the University Research Initiative of the U.S. Army Research Office.