On Timonov's algorithm for global optimization of univariate Lipschitz functions (Q1177913)

The authors consider the global maximization of a univariate Lipschitz function \(f\) over an interval \([a,b]\): \((*)\) \(\max\{f(x)\mid x\in[a,b]\}\). The function \(f\) satisfies the condition: \(\forall x,y\in[a,b]\) \(| f(x)-f(y)|\leq L| x-y|\) where \(L\) is a constant. Many algorithms have been proposed to solve \((*)\). \textit{L. N. Timonov} [Eng. Cybern. 15, No. 3, 38-44 (1977); translation from Tekh. Kibern. 15, No. 3, 53-60 (1977)] proposed an algorithm for \((*)\) close to that of \textit{S. A. Piyavskij} [U.S.S.R. Comput. Math. Math. Phys. 12(1972), No. 4, 57-67 (1973); translation from Zh. Vychisl. Mat. Mat. Fiz. 12, 888-896 (1972; Zbl 0249.65046)], but based on a completely different rationale. Namely, successive evaluation points are chosen in order to ensure at each iteration a maximal expected reduction of the ``region of indeterminacy'', which contains all global optimal points. It is shown that such an algorithm does not necessarily converge to a global optimum.