The method of global optimization of a function and estimation of the speed of its convergence (Q1342603)

For the global optimization problem \(f(x) \to \inf_{x \in \mathbb{R}^n}\) the following algorithm is given: Find \(x_{k + 1}\) such that \(x_{k+1} = x_k + \alpha_k \nabla \varphi_k (x_k)\), where \(f_{k+1} (x) := f_k(x) - c_k\) if \(f_k (x) \leq c_k\) and \(f_{k+1} (x):= 0\) if \(f_k(x) > c_k\), \(c_k = \int_{\mathbb{R}^n} f_k(\xi) p_k (\xi) d\xi\), \(\varphi_k(x) = \int_{\mathbb{R}^n} f_{k + 1} (\xi) G(x, \xi) p_k (\xi) d\xi\), and \(p_k(\xi)\) is the distribution density at the \(k\)th step and \(G(x,\xi)\) is the Green function for the Poisson equation \(\nabla \varphi = (f(x) - c) p(x)\). The author proves for this algorithm the following convergence theorem: The constructed sequence \(\{x_k\}\) converges only at the point \(x_*\) of global minimum of the function \(f\) with the error estimation \(|x_k - x_*|\leq \eta^k (\Delta_k) |x_1 - x_*|\). If the function \(f\) has several points of global minimum, the sequence may not converge at a point of global minimum. To ensure the convergence in this case, it is necessary to rearrange the densities \(p_k\).