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?