14
$\begingroup$

I am interested in globally maximizing a function of many ($\approx 30$) real parameters (a result of a complex simulation). However, the function in question is relatively expensive to evaluate, requiring about 2 days for each parameter set. I am comparing different options, and was wondering if anyone had suggestions.

I know there is a suite of methods for this sort of process that involve developing approximate functions and then maximizing those (e.g. Jones et al. "Efficient Global Optimization of Expensive Black-Box Functions"). However, this seems to be relatively involved to code.

I do have the ability to run a large number of simulations in parallel (50+). This seemed to suggest using something like genetic algorithms to do this optimization - since I can create a population of candidate solutions just as quickly as I can make one.

Here are my questions: 1) Does anyone have experiences with freely available implementations of this sort of global solvers / recommendations? 2) Are there reasons to either prefer or avoid genetic algorithms here?

This is a physical problem, and my early experiments have shown the figure of merit changes fairly smoothly as I change the parameters.

UPDATE:

Thank you for the help! A few more details: I do not need any information beyond the location of the maximum. The simulation is deterministic, not Monte Carlo, so that complication isn't a big deal. There are no explicit bounds or constraints on the parameters. One other piece of information I have (and didn't mention before) is a sense of the size of the maximum required. While I am looking for a global maximum, I would also be happy with anything of this scale or larger - I don't know if this would provide any help. Hopefully if I do the screening more systematically (Latin hypercubes as suggested by Brian Borchers), this will show up.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ When you evaluate the objective function, does it produce any additional information, esp. derivatives (or approximations) with respect to parameters? Since the objective function itself is expensive to compute, it might be that such computations need to be milked for supplementary information. $\endgroup$
    – hardmath ♦
    Commented Nov 19, 2013 at 17:08
  • 1
    $\begingroup$ (A year later), what did you end up doing -- varying a few of the 30 parameters, model ... ? $\endgroup$
    – denis
    Commented Nov 13, 2014 at 15:15
  • 1
    $\begingroup$ denis: I was able to use some physical intuition (and luck) to guess the most crucial parameters, and then vary them to get a "good enough" result. (In this case, finding the precise optimum wasn't as important as finding a large enough answer.) I didn't end up needing the full power of these techniques, but it's good to have them handy. $\endgroup$
    – AJK
    Commented Nov 18, 2014 at 0:13
  • 1
    $\begingroup$ Granted this was 2 1/2 years ago, but do you have a choice of accuracy level in your objective function evaluation (deterministic simulation), and can trade off accuracy vs. run time? $\endgroup$
    – Mark L. Stone
    Commented May 19, 2016 at 13:26

5 Answers 5

Reset to default
12
$\begingroup$

Genetic algorithms are a very poor choice when the objective function is extremely expensive to evaluate- these methods require a lot of function evaluations in each generation (which parallelism can help with) and a lot of generations (which are inherently sequential.) At two days per generation, this would be very slow.

You haven't mentioned where this problem came from. Are you statistically analyzing a likelihood surface (in which case you'll want more than just the optimal parameters and objective value) or just optimizing an objective function?

You haven't mentioned whether the objective function calculation is precise or inaccurate. It's often the case that when the objective function is calculated by Monte Carlo simulation, the values are quite noisy. This can mislead many optimization algorithms. Response surface methods help with this problem by smoothing out the noise.

You haven't mentioned any constraints on the parameters. Are they bounded? Are there linear or nonlinear constraints between the parameters?

Chances are that most of your 30 parameters aren't really that important to the problem. I would suggest using an experimental design screening approach to first determine which of the 30 parameters are really important in the optimization, and then after setting reasonable values for the unimportant parameters optimize over the important parameters. Methods like Latin Hypercube Sampling can be very helpful in screening out the relatively unimportant parameters. In this screening stage you can easily make use of hundreds of processors.

After reducing the number of parameters to a more reasonable size, I'd use a response surface method to optimize over the remaining parameters. If the response surface really is multi-modal, and you use an overly simple response surface model (typically folks just fit a quadratic model) then you could easily be mislead and miss out on the global maximum. Be careful! In this stage you can again make use of lots of processors by using an experimental design that gives very good coverage of the parameter space. Look for design points where the fitted model is far off from the computed values- this is an indication that the response surface isn't working well in that region. You may have to build response surfaces in separate regions of the parameter space.

As a last step, you can start with the parameters from your response surface optimization and try to improve on the values of the screened out parameters by adjusting them one at a time (coordinate descent.)

I'll second the recommendation of DAKOTA as a framework for this kind of optimization. If you're going to be doing this optimization only once then it might be easier to organize the computations by hand, but if you're going to do it repeatedly, then DAKOTA would be very helpful.

Improve this answer
$\endgroup$
6
$\begingroup$

  1. I don't have any experience with these sorts of solvers; some of my co-workers have used them. DAKOTA seems to be the software package recommended for these sorts of tasks. It includes an interface that allows a user to repeatedly submit jobs to a submission queue and use the output for parameter studies, sensitivity analysis, etc. I'm not familiar enough with it to know whether or not it will take advantage of running many simulations simultaneously.

  2. Assuming that your parameters are continuous, if the figure of merit changes smoothly as parameters change, then a surrogate model should do a reasonable job of fitting the figure of merit, and surrogate derivative information should be helpful for refining convergence. For 30 parameters, deterministic derivative-free optimization methods should also be useful; there again, smoothness should help. In contrast, genetic algorithms won't use derivative information at all, and often require tuning of parameters like mutation rate, recombination rate, and selection parameters in order to achieve good performance. As an algorithmic choice, I'd use genetic algorithms as a fallback, because I'd expect a well-designed surrogate optimization or a deterministic derivative-free optimization method to have better convergence behavior.

Improve this answer
$\endgroup$
2
  • $\begingroup$ A couple of reasons that using a deterministic derivative-free optimization method might not be wise. First, these are local search methods that may end up finding a local maxmimum and missing a much better point elsewhere in parameter space. Second, these methods typically require lots of iterations with relatively few function evaluations per iteration, so they don't parallelize well. $\endgroup$
    – Brian Borchers
    Commented Nov 17, 2013 at 16:39
  • $\begingroup$ You're right about local search methods. There are global search methods (DIRECT, branch-and-bound, multilevel coordinate search) that do not construct surrogate models and should behave better than local search methods. I can't speak to the efficacy of parallelizing these methods. $\endgroup$
    – Geoff Oxberry
    Commented Nov 17, 2013 at 19:48
2
$\begingroup$

Have a look at TOMLAB, DAKOTA, and OpenMDAO for black-box optimization.

Edit #3: Bayesian optimization is very similar to EGO:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

limited licenses:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint

Edit #2:

The first approach is to build a metamodel/surrogate (using kriging/GP) around expensive function and use this additional information to find the global optimum point faster and with fewer evaluations (EGO).

The second approach as in MDAS, is to do direct search with some clever adaptions on multiple levels.

Heuristic approaches are genetic/randomized in nature and without any guarantees.

Edit #1:

TOMLAB is MATLAB based tool that has the best speed / quality of optimization according to Sahinidis'es paper. But this is commercial tool with significant corporate usage. I'm not using this.

DAKOTA is more tailored for Uncertainty Quantification, besides general optimization. Based on c++ and some legacy Fortran code. Though under LGPL license and binaries available for download, very difficult to recompile at least from my experience on Win7 with GCC or MSVS/ifort. Has dependencies on boost, lapack, cmake for build. Basically this is a wrapper for numerous open source solvers and few commercial ones. This is SNL product and is tightly integrated with other projects from Sandia NL. I was able to successfully integrate this one instead of some IMSL routines. Sahinidis'es paper missed the massive parallelism possible with DAKOTA.

OpenMDAO is optimization based design software developed in Python by NASA under APACHE License. I'm trying this out currently.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Welcome to SciComp! As currently written, your post does not really explain why looking at TOMLAB or OpenMDAO would be a good idea (other answers already discuss DAKOTA). We're looking for answers that not only provided recommendations, but discuss why those recommendations are useful, potential pitfalls, and so on. $\endgroup$
    – Geoff Oxberry
    Commented Jun 11, 2014 at 23:42
  • $\begingroup$ I rushed with my answer first and now I added explaination. $\endgroup$
    – den.run.ai
    Commented Jun 12, 2014 at 2:47
0
$\begingroup$

If you can't afford 30 runs, each varying one parameter, vary them in groups:
for example, 8 runs each varying 4 parameters together, then refine the best 2 runs / 8 parameters ...
(I have no idea how to tradeoff info gain vs. total runtime; multi-armed bandit ?)

Improve this answer
$\endgroup$
-3
$\begingroup$

Here is a code that allows to efficiently optimize expensive black-box functions using multicore CPUs.

A description of mathematics behind the code is given here.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This is the same answer you provided in this post. Also, it seems that this is your own work. If that is true, please state that explicitly in your answer. $\endgroup$
    – nicoguaro ♦
    Commented May 19, 2016 at 1:42
  • $\begingroup$ Can you provide details about the approach described in the paper and implemented in the software? What is the method used? Why is it good? What is provided in this approach that the other answers don't cover? $\endgroup$
    – nicoguaro ♦
    Commented May 19, 2016 at 1:42
  • 1
    $\begingroup$ Also, please mention that you are the author of this software, so anyone reading this will be aware that you a) know what you're talking about and b) might be a bit partial. $\endgroup$
    – Christian Clason
    Commented May 19, 2016 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.