Global optimization by controlled random search

The paper describes a new version, known as CRS2, of the author's controlled random search procedure for global optimization (CRS). The new procedure is simpler and requires less computer storage than the original version, yet it has a comparable performance. The results of comparative trials of the two procedures, using a set of standard test problems, are given. These test problems are examples of unconstrained optimization. The controlled random search procedure can also be effective in the presence of constraints. The technique of constrained optimization using CRS is illustrated by means of examples taken from the field of electrical engineering.     

On the Markov homogeneous optimization method

Estimates of the convergence rate of some homogeneous Markov monotone random search optimization methods are given.     

On the convergence rate of the Markov homogeneous monotone optimization method

An estimate of the convergence rate of some homogeneous Markov monotone random search optimization algorithms is obtained.     

Properties of the random search in global optimization

From theorems which we prove about the behavior of gaps in a set ofN uniformly random points on the interval [0, 1], we determine properties of the random search procedure in one-dimensional global optimization. In particular, we show that the uniform grid search is better than the random search when the optimum is chosen using the deterministic strategy, that a significant proportion of large gaps are contained in the uniformly random search, and that the error in the determination of the point at which the optimum occurs, assuming that it is unique, will on the average be twice as large using the uniformly random search compared with the uniform grid. In addition, some of the properties of the largest gap are verified numerically, and some extensions to higher dimensions are discussed. The latter show that not all of the conclusions derived concerning the inadequacies of the one-dimensional random search extend to higher dimensions, and thaton average the random search is better than the uniform grid for dimensions greater than 6.This paper is based on work started in the Statistics Department of Princeton University when the first author was visiting as a Research Associate. Part of this research was supported by the Office of Naval Research, Contract No. 0014-67-A-0151-0017, and by the US Army Research Office—Durham, Contract No. DA-31-124-ARO-D-215.2 The authors wish to thank B. Omodei for his careful work in preparing the programs for the results of Figs. 1–2 and Table 1. The computations were performed on the IBM 360/50 of the Australian National University's Computer Centre. Thanks are also due to R. Miles for suggestions regarding the extension of the results to multidimensional regions, and to P. A. P. Moran and R. Brent for suggestions regarding the evaluation of the integral ₀ ¹ ... ^0/1 (x ₁ ² + ... +x _n ^/2 )^1/2 dx ₁ ...dx _n.     

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

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

Almost Surely Convergent Global Optimization Algorithm Using Noise-Corrupted Observations

A new recursive algorithm for searching the global minimizer of a function is proposed when the function is observed with noise. The algorithm is based on switches between the stochastic approximation and the random search. The combination of SA with RS is not a new idea in such combination, the difficulty consists in creating a good switching rule and in designing an efficient method to reduce the noise effect. The proposed switching rule is easily realizable, the noise reducing method is effective, and the whole recursive optimization algorithm is simply calculated. It is proved that the algorithm a.s. converges to the global minimizer and is asymptotically normal. In comparison with existing methods, the proposed algorithm not only requires much weaker conditions, but also is more efficient as shown by simulation.     

Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization

A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.     

Global search algorithms for minimum concave-cost network flow problems

We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.     

Stochastic processes with independent increments for random mappings

Using additive functions defined on the combinatorial structure of all mappings of anN set into itself, we define paths in the space endowed with the Skorokhod topology. Taking a mapping with equal probability, we get a sequence of random processes. Necessary and sufficient conditions for the weak convergence of this sequence to a stochastic process with independent increments are established. It is shown that the class of such processes contains all possible limits, provided that, on the components of a mapping, the additive functions have values small in average. Partially supported by the Lithuanian State Science and Studies Foundation. Vilnius University, Naugarduko 24, 2006 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 4, pp. 498–516, October–December, 1999. Translated by E. Manstavičius     

On Uniform Covering, Adaptive Random Search and Raspberries

The problem of generating a random sample over a level set, called Uniform Covering, is considered. A variant is discussed of an algorithm known as Pure Adaptive Search which is a global optimisation ideal with a desirable complexity. The algorithm of Uniform Covering by Probabilistic Rejection is discussed as an approach to the practical realisation of PAS. Consequences for the complexity and practical performance in comparison to other algorithms are illustrated.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

Continuous functions minimization by dynamic random search technique

Random search technique is the simplest one of the heuristic algorithms. It is stated in the literature that the probability of finding global minimum is equal to 1 by using the basic random search technique, but it takes too much time to reach the global minimum. Improving the basic random search technique may decrease the solution time. In this study, in order to obtain the global minimum fastly, a new random search algorithm is suggested. This algorithm is called as the Dynamic Random Search Technique (DRASET). DRASET consists of two phases, which are general search and local search based on general solution. Knowledge related to the best solution found in the process of general search is kept and then that knowledge is used as initial value of local search. DRASET’s performance was experimented with 15 test problems and satisfactory results were obtained.     

A nonmonotone line search based algorithm for distribution center location selected

The minimax optimization model introduced in this paper is an important model which has received some attention over the past years. In this paper, the application of minimax model on how to select the distribution center location is first introduced. Then a new algorithm with nonmonotone line search to solve the non-decomposable minimax optimization is proposed. We prove that the new algorithm is global Convergent. Numerical results show the proposed algorithm is effective.     

On geometric convergence rate of Markov search towards the fat target

Let $f:A\to \mathbb{R}$ be a continuous function with the minimal value $f^{?}$, where $A$ is the compact metric space. Let ${\left\{X_t\right\}}_{t\in \mathbb{N}}$ be a Markov chain which represents the global optimization process on $A$. We present sufficient conditions for very strong, geometric convergence mode of the form $Ef\left(X_t\right)?f^1\le c^t?(Ef\left(X_0\right)?f^1)$, where $c\in (0,1)$ is some constant. This convergence mode is natural if the set of global minima is fat.     

NA随机变量阵列的完全矩收敛性

利用NA随机变量的矩不等式和截尾方法,研究了NA随机变量阵列的完全矩收敛性,给出了证明NA随机变量阵列完全矩收敛性的一些充分条件.所得结果推广了已有文献关于NA随机变量的相应结果.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

On convergence rates of subgradient optimization methods

Rates of convergence of subgradient optimization are studied. If the step size is chosen to be a geometric progression with ratio the convergence, if it occurs, is geometric with rate. For convergence to occur, it is necessary that the initial step size be large enough, and that the ratio be greater than a sustainable ratez(), which depends upon a condition number, defined for both differentiable and nondifferentiable functions. The sustainable ratez() is closely related to the rate of convergence of the steepest ascent method for differentiable functions: in fact it is identical if the function is not too well conditioned.This research was supported in part by the D.G.E.S. (Quebec) and the N.R.C. of Canada under grants A8970 and A4152.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.