Convergence rates of a global optimization algorithm (Q1186279): Difference between revisions

This paper presents a best and worst case analysis of convergence rates for a deterministic global optimization algorithm published recently by the author [ibid. 34, 188-200 (1986; Zbl 0598.90075)], which is the \(N\)- dimensional extension of the Pijavskij-Shubert algorithm [see \textit{S. A. Pijavskij} [Zh. Vychislit. Mat. Mat. Fiz. 12, 888-896 (1972; Zbl 0249.65046); English translation in U.S.S.R. Comput. Math. Math. Phys. 12(1972), No. 4, 57-67 (1973)], and \textit{B. O. Shubert} [SIAM J. Numer. Anal. 9, 379-388 (1972; Zbl 0251.65052)]. Superlinear convergence is proved for Lipschitz functions which are convex in the direction of the global maximum (concave in the direction of the global minimum). In verifying computationally the expected convergence rates the author used the program he has implemented on a VAX 11-780 and the following test functions: \[ \text{Invert}(x)=1-{\sqrt N\over N}\| x^*- x\|,\quad 0\leq x^ i\leq 1, x^*=(1,\dots,1),\quad\text{and} \] \[ \text{Expo}(x)=e^{-\| x^*-x\|},\quad 0\leq x^ i\leq 1, x^*=(1,\dots,1). \] Computational results are given which confirm the theoretical convergence rates.