Theory of Global Random Search

1 Global Optimization: An Overview.- 1. Global Optimization Theory: General Concepts.- 1.1. Statements of the global optimization problem.- 1.2. Types of prior information about the objective function and a classification of methods.- 1.2.1. Types of prior information.- 1.2.2. Classification of principal approaches and methods of the global optimization.- 1.2.3. General properties of multiextremal functions.- 1.3. Comparison and practical use of global optimization algorithms.- 1.3.1. Numerical comparison.- 1.3.2. Theoretical comparison criteria.- 1.3.3. Practical optimization problems.- 2. Global Optimization Methods.- 2.1. Global optimization algorithms based on the use of local search techniques.- 2.1.1. Local optimization algorithms.- 2.1.2. Use of local algorithms in constructing global optimization strategies.- 2.1.3. Multistart.- 2.1.4. Tunneling algorithms.- 2.1.5. Methods of transition from one local minimizer into another.- 2.1.6. Algorithms based on smoothing the objective function.- 2.2. Set covering methods.- 2.2.1. Grid algorithms (Passive coverings).- 2.2.2. Sequential covering methods.- 2.2.3. Optimality of global minimization algorithms.- 2.3. One-dimensional optimization, reduction and partition techniques.- 2.3.1. One-dimensional global optimization.- 2.3.2. Dimension reduction in multiextremal problems.- 2.3.3. Reducing global optimization to other problems in computational mathematics.- 2.3.4. Branch and bound methods.- 2.4. An approach based on stochastic and axiomatic models of the objective function.- 2.4.1. Stochastic models.- 2.4.2. Global optimization methods based on stochastic models.- 2.4.3. The Wiener process case.- 2.4.4. Axiomatic approach.- 2.4.5. Information-statistical approach.- 2. Global Random Search.- 3. Main Concepts and Approaches of Global Random Search.- 3.1. Construction of global random search algorithms: Basic approaches.- 3.1.1. Uniform random sampling.- 3.1.2. General (nonuniform) random sampling.- 3.1.3. Ways of improving the efficiency of random sampling algorithms.- 3.1.4. Random coverings.- 3.1.5. Formal scheme of global random search.- 3.1.6. Local behaviour of global random search algorithm.- 3.2. General results on the convergence of global random search algorithms.- 3.3. Markovian algorithms.- 3.3.1. General scheme of Markovian algorithms.- 3.3.2. Simulated annealing.- 3.3.3. Methods based on solving stochastic differential equations.- 3.3.4. Global stochastic approximation: Zielinski's method.- 3.3.5. Convergence rate of Baba's algorithm.- 3.3.6. The case of high dimension.- 4. Statistical Inference in Global Random Search.- 4.1. Some ways of applying statistical procedures to construct global random search algorithms.- 4.1.1. Regression analysis and design.- 4.1.2. Cluster analysis and pattern recognition.- 4.1.3. Estimation of the cumulative distribution function, its density, mode and level surfaces.- 4.1.4. Statistical modelling (Monte Carlo method).- 4.1.5. Design of experiments.- 4.2. Statistical inference concerning the maximum of a function.- 4.2.1. Statement of the problem and a survey of the approaches for its solution.- 4.2.2. Statistical inference construction for estimating M.- 4.2.3. Statistical inference for M, when the value of the tail index ? is known.- 4.2.4. Statistical inference, when the value of the tail index ? is unknown.- 4.2.5. Estimation of F(t).- 4.2.6. Prior determination of the value of the tail index ?.- 4.2.7. Exponential complexity of the uniform random sampling algorithm.- 4.3. Branch and probability bound methods.- 4.3.1. Prospectiveness criteria.- 4.3.2. The essence of branch and bound procedures.- 4.3.3. Principal construction of branch and probability bound methods.- 4.3.4. Typical variants of the branch and probability bound method.- 4.4. Stratified sampling.- 4.4.1. Organization of stratified sampling.- 4.4.2. Statistical inference for the maximum of a function based on its values at the points of stratified sample.- 4.4.3. D