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.     

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.     

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.     

A stopping rule for a compound poisson random variable

An optimal empirical Bayesian stopping rule for the Poisson compounded with the geometric distribution is developed and applied to the problem of the sequential testing of computer software. For each checkpoint in time, either the software satisfies a desired economic criterion, or else the software testing is continued.     

Bayesian Stopping Rules for Greedy Randomized Procedures

A greedy randomized adaptive search procedure (GRASP) is proposed for the approximate solution of general mixed binary programming problems (MBP). Examples are provided of practical applications that can be formulated as MBP requiring the solution of a large number of problem instances. This justifies, from both a practical and a theoretical perspective, the development of stopping rules aimed at controlling the number of iterations in a GRASP. To this end, a bayesian framework is laid down, two different prior distributions are proposed and stopping conditions are explicitly derived in analytical form. Numerical evidence shows that the stopping rules lead to an optimal trade-off between accuracy and computational effort, saving from unneeded iterations and still achieving good approximations.     

On the robustness of Bayesian networks to learning from non-conjugate sampling

Recent results concerning the instability of Bayes Factor search over Bayesian Networks (BN’s) lead us to ask whether learning the parameters of a selected BN might also depend heavily on the often rather arbitrary choice of prior density. Robustness of inferences to misspecification of the prior density would at least ensure that a selected candidate model would give similar predictions of future data points given somewhat different priors and a given large training data set. In this paper we derive new explicit total variation bounds on the calculated posterior density as the function of the closeness of the genuine prior to the approximating one used and certain summary statistics of the calculated posterior density. We show that the approximating posterior density often converges to the genuine one as the number of sample point increases and our bounds allow us to identify when the posterior approximation might not. To prove our general results we needed to develop a new family of distance measures called local DeRobertis distances. These provide coarse non-parametric neighbourhoods and allowed us to derive elegant explicit posterior bounds in total variation. The bounds can be routinely calculated for BNs even when the sample has systematically missing observations and no conjugate analyses are possible.     

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.     

用于连续抽样方案的两类更优的中止规则

本文提出并讨论了适用于各类连续抽样方案的两参数中止规则 [N ,c]和 [R ,d]。作为应用 ,以MIL STD 12 35B中公布的CSP V方案为例 ,计算并给出了相应的中止参数 ,还将 [N ,c],[R ,d]与已有的两类规则 [S],[R]进行了特性比较。结果表明 ,[N ,c]和 [R ,d]均具有更优的统计特性     

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 general method for finding the optimal threshold in discrete time

We develop an approach for solving one-sided optimal stopping problems in discrete time for general underlying Markov processes on the real line. The main idea is to transform the problem into an auxiliary problem for the ladder height variables. In case that the original problem has a one-sided solution and the auxiliary problem has a monotone structure, the corresponding myopic stopping time is optimal for the original problem as well. This elementary line of argument directly leads to a characterization of the optimal boundary in the original problem. The optimal threshold is given by the threshold of the myopic stopping time in the auxiliary problem. Supplying also a sufficient condition for our approach to work, we obtain solutions for many prominent examples in the literature, among others the problems of Novikov-Shiryaev, Shepp-Shiryaev, and the American put in option pricing under general conditions. As a further application we show that for underlying random walks (and Lévy processes in continuous time), general monotone and log-concave reward functions g lead to one-sided stopping problems.     

Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).     

Bayesian Algorithms for One-Dimensional Global Optimization

In this paper Bayesian analysis and Wiener process are used in orderto build an algorithm to solve the problem of globaloptimization.The paper is divided in two main parts.In the first part an already known algorithm is considered: a new (Bayesian)stopping ruleis added to it and some results are given, such asan upper bound for the number of iterations under the new stopping rule.In the second part a new algorithm is introduced in which the Bayesianapproach is exploited not onlyin the choice of the Wiener model but also in the estimationof the parameter ² of the Wiener process, whose value appears to bequite crucial.Some results about this algorithm are also given.     

A Practical Sequential Stopping Rule for High-Dimensional Markov Chain Monte Carlo

A current challenge for many Bayesian analyses is determining when to terminate high-dimensional Markov chain Monte Carlo simulations. To this end, we propose using an automated sequential stopping procedure that terminates the simulation when the computational uncertainty is small relative to the posterior uncertainty. Further, we show this stopping rule is equivalent to stopping when the effective sample size is sufficiently large. Such a stopping rule has previously been shown to work well in settings with posteriors of moderate dimension. In this article, we illustrate its utility in high-dimensional simulations while overcoming some current computational issues. As examples, we consider two complex Bayesian analyses on spatially and temporally correlated datasets. The first involves a dynamic space-time model on weather station data and the second a spatial variable selection model on fMRI brain imaging data. Our results show the sequential stopping rule is easy to implement, provides uncertainty estimates, and performs well in high-dimensional settings. Supplementary materials for this article are available online.     

An optimal sequential procedure for a multiple selling problem with independent observations

We consider a sequential problem of selling K identical assets over the finite time horizon with a fixed number of offers per time period and no recall of past offers. The objective is to find an optimal sequential procedure which maximizes the total expected revenue. In this paper, we derive an effective number of stoppings for an optimal sequential procedure for the selling problem with independent observations.     

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.     

一维扩散过程的最优停止问题的研究

本文研究了一维扩散过程的最优停止问题,论证了W iener过程和几何布朗运动是F e ller过程,同时给出了一般扩散过程的处理方法.     

中止规则的平均延迟时间及其应用

本文以平均延迟时间为度量，对适用于连续抽样方案的四种中止规则，即规则［Ｓ］，［Ｒ］，［Ｎ，ｃ］及［Ｒ，ｄ］的中止“速度”进行了比较。结果表明：［Ｒ］优于［Ｓ］，而［Ｎ，ｃ］与［Ｒ，ｄ］均优于［Ｒ］。这些结论及方法可被用来适当地选择中止规则，以提高连续型生产的质量控制水平     

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.     

The monotone case approach for the solution of certain multidimensional optimal stopping problems

This paper studies explicitly solvable multidimensional optimal stopping problems of sum- and product-type in discrete and continuous time using the monotone case approach. It gives a review on monotone case stopping using the Doob decomposition, resp. Doob–Meyer decomposition in continuous time, also in its multiplicative versions. The approach via these decompositions leads to explicit solutions for a variety of examples, including multidimensional versions of the house-selling and burglar’s problem, the Poisson disorder problem, and an optimal investment problem.