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

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?

• Is it possible for you to translate those fixed boundaries for the variables into constraints for the optimization problem? Also, did you have a look at variable-step solvers? They could save you some executions in contrast to fixed-step ones. Besides that I'm not aware of specific solvers for this case, often people just deploy more computation power to solve the issue. – deemel Jul 13 '18 at 7:09
• Is there an option to speedup the function calculation? Like, using a GPU or a cluster, etc.? – stan0 Jul 13 '18 at 9:19
• @stan0 yes this is in the working, but this question is particular about the algorithm – Christian Jul 13 '18 at 9:32
• In contrast to the answers above I have to say that there are dedicated algorithms in order to execute just the task that you describe. They are usually used in order to optimize the hyperparameters of a neural net. They go like this: approximate the function, optimize the approximated function and then take the minimum of that as the next candidate. One possibility to do this is Gaussian Processes: arimo.com/data-science/2016/… – Fabian Werner Jul 13 '18 at 10:43
• I think that the name of the field dedicated to optimizing costly functions is called „Bayesian optimization“ googling for that will lead you (for example) to the R package rBayesianOptimization. They have implemented Gaussian process optimization. – Fabian Werner Jul 13 '18 at 10:45

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:

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.

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