# What kind of optimisation algorithm is suitable for a computationally expensive function?

I have a reference value $R$ and a modelled value $M$. $M$ is generated using a stochastic algorithm with parameters $a$ and $b$.

The objective is to tune $a$ and $b$ so that $M$ is as close as $R$ possible (heuristically). But each run of $M$ takes around 30 seconds. Any "good" algorithm will be jammed by this computation, seemingly. Even so, what is better (than others) algorithm of choice?

If we are to allow $\vert M-R\vert$ converges quickly initially (and accept it to slowly converge in later stages), what types of algorithm should I look for? My colleague suggests Particle Swarm Optimisation (PSO). Is that a good choice?

Note: We need "good" fit but not "best" fit. Our tolerance is fairly large.

## 2 Answers

Response surface models (a kind of surrogate model) are often used in situations like this. The idea is to sample values of the parameters $a$ and $b$, compute $R(a,b)$ at each point, and then build a regression model (typically quadratic or even higher order) of the function. You can then optimize over the the fitted model.

• You can even improve the fit of the regression model each time you evaluate $R$ at the values $a$ and $b$ corresponding to the optimum of the current regression model. – fibonatic May 14 '16 at 21:05
• I would like to use the algorithm in R (The R Project, not $R(a,b)$ in the above). Which package is good? – user2513881 May 17 '16 at 5:29
• I'm not enough of an R expert to help you with that. – Brian Borchers May 17 '16 at 16:25
• Just for others' interest, DiceOptim and DiceKriging seem to be good packages to handle model building, confidence intervals and expected improvements. – user2513881 Jun 1 '16 at 4:01

Active learning (aka experimental design) strategies are suitable for this. One of them being the response surface modeling suggested by Brian Borchers. The idea is to choose the next point to evaluate to learn about the optimal M as fast as possible. Here are some old and new papers to start from:

• Harold J. Kushner. A new method of locating the maximum of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, pages 86:97–106, March 1964.
• J. Mockus. The Bayesian approach to global optimization. Lecture Notes in Control and Information Sciences, 38:473–481, 1982.
• Julien Villemonteix, Emmanuel Vazquez, and Eric Walter. An informational approach to the global optimization of expensive-to-evaluate functions. Journal of Global Optimization, September 2008, cs/0611143.