On the rate of convergence of one inhomogeneous Markov algorithm of search for extremum
A. S. Tikhomirov · Vestnik St Petersburg University Mathematics · 2011
The paper is concerned with theoretical study of the rate of convergence of one inhomogeneous Markov random algorithm of search for extremum. Methods of random search have value in solving involved optimization problems. However, there are only few theoretical results concerning the rate of convergence of these algorithms. Suppose that an objective function f assumes its minimal value at a unique point x *. Random search is useful in searching for a global minimum point x * with given accuracy ɛ. As a characteristic of the rate of convergence of an algorithm, we use the number of evaluations of the objective function required to attain the given accuracy ɛ of solution. In this paper, theoretical estimates for the rate of convergence are obtained and further used to build asymptotically fast optimization methods. The number of evaluations of a “nondegenerate” objective function required to attain the given accuracy ɛ is shown to be of order O(|lnɛ|ln|lnɛ|) as ɛ → 0. Note that many local optimization methods (like the method of steepest descent) require O(|lnɛ|) steps to enter the ɛ-neighborhood of x *; however, in these methods the objective function is subject to much more stringent restrictions. In global optimization problems, the order for the number of iterations is typically much worse; it is O(1/ɛα) for some α > 0. Consequently, the Markov random search constructed here is asymptotically fast, its asymptotic rate of convergence is just a little lower than that of the classical method of descent in the conventional local optimization problem.