A lower bound on complexity of optimization under the \(r\)-fold integrated Wiener measure (Q544129)

The global optimization problem is to approximate the minimum of a function that may have more than one local minimum. The author considers how many function or derivative evaluations are required in order to obtain an \(\varepsilon\) approximation to the global minimum. The paper presents the problem of approximating the global minimum of an \(r\)-times continuously differentiable function on the unit interval, based on sequentially chosen function and derivative evaluations. Using a probability model based on the \(r\)-fold integrated Wiener measure, a lower bound on the expected number of function evaluations required to approximate the minimum to within \(\varepsilon\) on average is estimated.