
Author(s)  Zhigljavsky, A. A. 

Title  Theory of Random Global Search 
Publisher  Kluwer Academic Publishers 
Year of publication  1991 
Reviewed by  Mirela Stefanescu 
In the last decades , the stochastic approaches based on a probabilistic analysis of computational processes are of great efficiency, being natural for investigating highdimensional problems where the deterministic solution techniques are often inefficient. A. A. Zhigljavsky has studied probabilistic global optimization algorithms in which the evolution of probabilistic distributions corresponding to the computational process is also considered. Some of the algorithms appear here for the first time in the literature under a very rigorous form.
An overview of the problem of global optimization is the subject of the first part of the book. Some general concepts and their main properties are treated in the starting chapter: possibilities of stating the global optimization problem, types of prior information about the objective function and a classification of methods, general properties of multiextremal functions, comparison and practical use of global optimization algorithms.
Which are the methods in global optimization? One can use algorithms based on local search techniques or set covering methods like grid algorithms, sequential covering methods, onedimensional optimization (reduction and partition techniques, branch and bound methods). Stochastic models and an axiomatic approach for the objective function are also studied in this first part of the book. In this way, the part 1 of the present book attempts to elucidate the current stateofart in global optimization theory. Being impossible to describe all known solution approaches, we have to underline that the survey is rather complete and very general. The choice of the method for solving the global optimization is made upon heuristical, numerical and theoretical reasons. Sometimes global search methods offer the unique way of solving complicated problems. A random search choice of solutions is under uncertainty; let us remember the vital situations when choice was conditioned by cointossing.
The construction of global search algorithms, general results on their convergence, Markovian algorithms, with special reference to Zielinski's method and the convergence rate of Baba's algorithm are presented in Part 2. The main popularity reason of global random search methods among users are due to the following attractive features which many of them possess: the structure of these methods is rather simple and they can be easily realized as subroutines, they are rather insensitive to irregularity of the objective function behavior, as well as to the presence of noise in the objective function evolutions and also to the growth of dimensionability. Besides, it is easy to construct methods that guarantee global convergence or to realize various adaptation ideas. As for theoreticians, the global random search methods represent a rich and not very complicated subject matter for investigation and possible inclusion of statistical concepts and procedures.
There are also some disadvantages of these methods: the standard convergence rate of them is slow and it may be generally increased only if the probability of failure in reaching the extremum is allowed to increase. Moreover, these methods involve heuristic elements, while their efficiency can often be improved by means of increasing complexity and decreasing their randomness. Thus, one uses global random search only when the optimization problem is complicated enough but the objective function evaluation is not very timeconsuming. The author describes statistical inference in global random search (Chapter 4). This topics did not appear in the Russian edition and the chapter is new, written for the English version, containing not only the author's results concerning that subject, but also results obtained by many other mathematicians. By describing algorithms and formulation of the basic probabilistic model, some methods of generation for eigenmeasure functional estimation of linear integral operators and sequential analogues of such methods are given in Chapter 5.
Specific problems with their random search algorithms are treated in Chapter 6: constrained optimization problems and optimization in functional spaces, discrete and multicriterial optimization problems.
The global random search theory is connected with several other branches of mathematical statistics and computational mathematics; these relationships are studied in Part 3, where the biggest chapter is devoted to statistical inference for the bounds of random variables. Some other topics here are concerned with optimal design in extremal experiment, optimal simultaneous estimation of several integrals by the Monte Carlo methods, projection estimation of multivariate regression.
Nearly half of the mathematical content of the book is due to own researches of the author. Many sections of the book can be read almost independently, not only by theoreticians, but also by users of the optimization algorithms.
Certainly, the book will be of great interest to all mathematicians whose work involves global optimization.