Optimization algorithm where calculating the function is very costly [duplicate]

Question

I am doing physics simulation and have to minimize a function $f$ of approx. 10 parameters $f=f(x_1, x_2, ... , x_{10} )$. I have already looked into several optimization algorithms (downhill-simplex, stochastic gradient descent, Adam, ...). The general problem for my specific case is that 'calculating' the function $f$ with one set of parameters $x_1 ... x_{10}$ means doing a full simulation which needs about 10 minutes to finish. The function is smooth (although a bit noisy) and I can define fixed boundaries for all parameters $x_i$ out of which the result becomes unphysical.

So, is there any optimization algorithm that specifically works well for the case where calculating the function is very costly?

Answer 1

In general, optimization methods do not care about computational cost when computing the objective function. However, there are some strategies to deal with this case, which usually can be used with any optimization method.

For references, you can read some papers:

• Efficient optimization of computationally expensive objective functions
• Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions

Note that, there are many ways to realize a speedup strategy. For example, with the strategy of approximating the objective function. The first cited paper above uses recursive surrogate objective function. Another common way is Bayesian approximation by Gaussian process, combining it with an exploration-exploitation strategy to guess the optima position (not using gradient information) resulting in Bayesian optimization approach, as suggested by @FabianWerner in comment. For your specific problem, you can choose which speedup strategies and optimization method you want to use and how to realize them.

In deep learning, a general strategy is to do massive parallelizing. For example, generating self-play games in AlphaZero is done on multiple GPUs/TPUs. Parameter update is usually only partially synchronized, but it will eventually approximately converge.

Answer 2

I don't think there is a dedicated algorithm for computationally heavy cost functions. Still, there are some things you could consider using the "usual" ones. For example:

• Prefer an optimisation algorithm that converges/descends faster, e.g. use Adam (or just momentum), instead of simple Gradient Descent
  • This would help your model move faster down the slope which means it would use less iterations and make less cost computations
• Experiment with larger learning rate, at least in the beginning
  • this would make your model "jump" further and probably go down to the minimum faster too. Of course this increases the risk of divergence so you have to be more careful while searching for the proper value