Randomized algorithm for global optimization with bounded memory (Q974238)

A class of adaptive algorithms is presented for approximating point \(t^*\), at which the global minimum \(f^*\equiv f(t^*)\) of a given function \(f(t)\) on a compact set \(A\), \(A\subset\mathbb{R}^d\) is attained. It is assumed that function \(f(t)\) satisfies only minimal regularity condition and attains its global minimum at a unique point \(t^*\in A\). The proposed approximation method is based on observation of function values \(f(t_i)\), \(i=1,\dots,n\) at sequentially selected points \(t_i\in A\), \(i= 1,\dots,n\). After \(n\) such observations, the algorithm chooses point \(t_{n+1}\in A\) as a function of previous points \(t_i\), \(i= 1,\dots,n\) and some auxilliary randomization. The memory, where the observations are stored is bounded so that it must be decided where to search next and which information to keep and which to discard. The author shows that by choosing a large enough memory, the convergence rate can be made to exceed any power of convergence obtained with standard Monte Carlo search.