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

Question

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?

Answer 1

Your estimate refers more to the number of function evaluations required to build a quadratic surrogate model for BOBYQA. Derivative-free methods that build surrogate models have to take a certain number of function evaluations to construct the surrogate model in order to do optimization. This number of function evaluations is the minimum number needed to take one step. In some surrogate modeling methods, it is possible to reuse some function evaluations and augment those with a number of new function evaluations to construct a new surrogate model. No such reuse is possible when initializing the algorithm, though.

ORBIT, which is based on using radial basis function surrogate models, requires fewer evaluations to construct a surrogate model (it's linear in the number of state variables). I don't know of a publicly available implementation. Part of the reason Powell's methods tend to be recommended is because library-quality implementations are available.

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).