Analysis of search methods of optimization based on potential theory. I: Nonlocal properties (Q1922434)

A deterministic optimization problem of minimizing a nonsmooth multiextremal function \(f:\mathbb{R}^n\to\mathbb{R}\) is considered. Evidently, this problem can be (from the numerical point of view) very complicated. The authors replace the original deterministic problem by a stochastic optimization one of minimizing \(Ef(X)\), where \(X\) is an \(n\)-dimensional random vector; \(E\) denotes the operator of mathematical expectation. To find a solution they use a random process in discrete time \(N=0,1,\dots\) \[ X^{N+1}=X^N+\alpha_NY^{N+1}, \qquad \alpha_N>0, \quad E|X^0|<\infty, \quad E|Y^1|<\infty, \] (\(Y^{N+1}\) defines the direction of search at the step \(N\)). Moreover, they introduce assumptions under which the trajectories of the random process \(X^N\) leave a nonperspective domain almost surely in a finite time. To this end, the potential theory is employed. A relationship between the Newtonian potential (generated by the objective function) and Lyapunov functions is shown. The paper is a continuation of the authors' former papers. In particular, it investigates the convergence methods presented in these former papers. The next investigation in this direction can be found in Part II reviewed below [Autom. Remote Control 55, No. 10, 1446-1451 (1994)].