Random Search Methods for Global Optimization—Basics

Random Search Methods for solving deterministic optimization problems, as arising in the deterministic substitute problems of stochastic optimization and stochastic optimal control problems, are considered in this chapter and Chaps. 5 – 7 . Besides mathematical optimization techniques, one of the major methods for solving deterministic parameter optimization problems is random search methods (RSM), for the following reason: Solving optimization problems from engineering and economics, one meets often the following situation: One should find the global optimum, hence, most of the deterministic programming procedures, which are based on local improvements of the performance index F(x), will fail: Concerning the objective function F one has a black-box—situation, i.e., there is only few a priori information about the structure of F, especially there is no knowledge about the direct functional relationship between the control or input vector $$x \in D$$ x ∈ D and its index of performance F(x); hence—besides the more or less detailed a priori information about F—the only way of getting objective information about the structure of F is via evaluations of its values F(x) by experiments or by means of a numerical procedure simulating the technical plant. After explaining the basic (RSM)-algorithm, conditions are presented guaranteeing the convergence, in some stochastic sense, of the search method to a global optimum. As an example, the random search method bis applied to discrete optimization problems. Since, especially toward the optimum, the speed of convergence may become rather low, possibilities for acceleration of (RSM) are considered. A basic method, which will be further developed in the next chapters, is to control the distribution of the search variates.