MATHEMATICAL MODELING

Method of Monte Carlo batch iteration to solving by global optimization problems

B. S. Darkhovskii, A. Yu. Popkov, Yu. S. Popkov

Institute for Systems Analysis of Russian Academy of Sciences

Abstract: This paper proposes a new solution method for global optimization problems involving Holder-functions defined on compact sets that are defined by algorithmically. The method is based on Monte Carlo batch iteration and constructing the sequences of “quasiglobal” minima and the sequence of their decrements. The latter serves for estimating the Holder constants of a goal function. We explore the probabilistic properties of the above sequences and demonstrate that this method possesses exponential convergence with the probability of 1 (almost sure). Under a finite number of iterations, we obtain the upper estimates for the distance between “quasiglobal” and exact solutions of the global minimization problem, as well as the lower estimates for the associated probability. And finally, a series of test problems illustrate the operability of the suggested technique.

Keywords: global optimization, canonical-form global optimization problems, transformation to unit nonnegative cube, Holder constants, module of continuity, Monte Carlo method, burst iterations, probabilistic convergence, the sequence of “quasiglobal” minima, the sequence of decrements, Monte Carlo estimates.