On the crude multidimensional search (Q1893557)

Multivariable trial functions that depend on random parameters are maximized by a crude global search. A crude search in an \(n\)-dimensional cube of large \(n\), say \(n > 4\), is regarded as inefficient since if the set of functions with bounded first partial derivatives is considered and \(N\) optimal searching points are selected, the convergence rate is only \(N^{-1/n}\). However, it was shown by I. Sobol' that the last estimate cannot be improved for ``bad'' functions only and these are functions equally depending on all \(n\) variables. It is clear, that if the function depends strongly on few of these variables, say \(m\) and \(m \ll n\), the convergence rate may be much better, even \(N^{-1/m}\). In this paper the dependence of error distributions on \(m\) (the effective number of leading variables) is investigated. It is recommended to use computational algorithms that are ``uniformly good'' (i.e. do not depend on the number of leading variables) rather than optimal algorithms whose construction relies upon the unknown bounds of partial derivatives.