# How does the number of iteration until optimization begins depends on the dimension of the problem?

I am optimizing a function of 10-20 variables by running algorithm such as BOBYQA and a few other derivative-free algorithms. The bad news is that each function evaluation is very expensive, approx 30 min of computation. The good news is that I start in the ballpark of the global minimum, and just a few moves in the "right direction" should suffice.

The problem is: I don't know how many function evaluation is required to start moving in the "right direction". My naive estimate is something like $n^2+n+1$: you've got to evaluate at initial point plus $2n$ points for 1st and 2nd derivatives in each of the $n$ directions plus $n(n-1)$ to evaluate mixed 2nd derivatives, and then you can make the 1st fairly confident step in the "right direction".

On the other hand, the above estimate, which is quadratic in the number of variables, seems excessive. I doubt one really needs that much info to start going toward local minimum. Thus the question: Given a well behaved problem in a general vicinity of the global minimum, after how many iterations would derivative-free optimization methods (such as Powell's ones) are expected to start moving toward local minimum for a function of $n$ variables?

When it comes to optimization iterations -- not function evaluations -- it is possible under certain assumptions to bound the number of iterations required to reach $\varepsilon$-optimality. There's a famous proof by Kantorovich that does so for Newton's method under some assumptions. I don't know of a result specifically for derivative-free optimization. We do know, for instance, that nonconvex optimization is NP-hard, so I would expect that any such result would require convexity, probably along with a number of technical conditions (like Kantorovich's proof, and Nesterov and Nemirovskii's result for interior point methods for convex nonlinear programs).