Optimal order of accuracy of search algorithms in stochastic optimization (Q749450)

Consider min\(\{\) f(x): \(x\in Q\subset R^ N\}\) with f: \(R^ N\to R^ 1\). Assume the unique existence of a solution. f is unknown and observations \(y_ n=f(x_ n)+\xi_ n\) with random errors \(\xi_ n\) are possible. The following random search algorithm is discussed: \[ z_ 0=b\quad (given),\quad x_ n=z_{n-1}+h_ n\psi_ n\quad (h_ n>0), \] \[ z_ n=\Pr_{Q_ n}(z_{n-1}-an^{-1}h_ n^{-1}y_ nK(\psi_ n))\quad (a>0), \] where \(\psi_ 1,\psi_ 2,..\). are independent random variables uniformly distributed on [-1/2, \(1/2]^ N\), \(Q_ n=Q\) convex, compact, Pr is the projection operator, K(t) is a vector function with components of the form \[ K_ j(t)=K_ 0(t_ j)\prod^{N}_{m\neq j}\tilde K(t_ m)\quad (j=1,...,N). \] Under some regularity conditions on f it is proved that the convergence order is not higher than \(O(n^{-(\beta -1)/\beta})\) where it is assumed that \[ | f(z)-\sum_{| m| \leq 1}\quad (m!)^{-1}D^ mf(x)(z-x)^ m| \leq L| z-x|^{\beta}. \]