Derivative free optimisation with over 100 variables

I have a problem for which I need to optimize more than a 100 variables with a derivative free method. Please note that the function used is a simulation that takes almost a minute to run. Which Matlab optimization tool would be the best for me ?

[Torsten]

Derivative-free optimization with more than 100 variables ?

You are kidding, aren't you ?

Best wishes

Torsten.

[John D'Errico]

Which optimization tool? I'd suggest prayer. Willful, earnest prayer. Sadly, the prayer toolbox is only in beta test, so you may not have a prayer. Have you considered a tithe to MathWorks? It might help. ;-)

Really, any optimization tool will work, as long as your function is continuous and differentiable. It will just take some time. (But NOT fminsearch.) Fminunc will perform numerical differentiation with finite differences. So about 1.5 hours just to compute a gradient. Hey, this is your problem, chosen by you to deal with in this way, not mine!

Or you can use a tool from the Global optimization toolbox. Still gonna take serious time. Buy a faster computer. Spend some time optimizing your code to be more efficient.

It is not clear if your function is a stochastic one or not. You mentioned the word simulation. So is there simulation noise in it? If so, then fminunc is out. In fact, almost any optimizer is highly problematic on a noisy function. This is because a basic tenet of optimization methods is that the function is at least continuous. Differentiable would be nice. Add noise in there, and you are somewhat screwed.

On a noisy function, you will need to do some variety of response surface optimization. So at any location, build a local model. This will take more effort than just computing a gradient of course, which is implicitly a first order model, but with noise, the basic finite difference schemes will fail.

Tools like genetic algorithms might help, but they too assume that your function is repeatable. If you think about it, genetic algorithms are based on optimization of a noisy process, with zillions of parameters. But, true genetic optimization has the good fortune to have billions of years to converge. Ok, I'll concede that SOME people think it might need only 6000 years. Still a long time. ;-)

So, this brings us back to prayer.

Answer 1

[Alan Weiss]

While the other comments have largely been negative, I think that you might have some luck using patternsearch with the Cache option. Typically, Cache does not work well, but when the objective function takes a minute to evaluate, well, I think you should use it. Be prepared to wait for a few days for a result, because computing even one complete pattern could take 100 minutes ~ 2 hours.

You didn't say whether you have any nonlinear constraints. If you do, then even patternsearch might be too slow.

Be sure to use a plot function or an output function to monitor the optimization and to log intermediate results.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Lukas Öhlund]

I know this question is a bit old, but I thought I'd share my view of it.

It is definitely possible, but it is going to take a long time. Alan said days, I will say weeks (depending on how "optimized" you want your solution to be).

Pattern search is good and worth trying. Gaussian adaption might work if you have a "nice" cost-function surface (https://mosaic.mpi-cbg.de/?q=downloads/Gaussian_adaptation), the same goes for BOBYQA (https://en.wikipedia.org/wiki/BOBYQA). Genetic algorithm is probably your best choice when it comes to formal optimization methods.

However, the best approach that I have found is to randomize...

This might seem to be very time-inefficient but if you put some thought into the way you randomize it can in some optimization problems be superior. The basic principles should look something like this:

1. Generate a huge amount of random set of optimization values (lets call them X) distributed over your feasible region.
2. Pick the N best set of X. (N could be 1 or ~100, or whatever)

For each N:

• Randomize with a (quite wide) normal distribution around X and evaluate your cost function. Do this for ~1/3 of samples compared to step 1 above.
• Pick the new best X and repeat the bullet above with a narrower normal distribution.

You are most likely going to end up with N different solutions which you can manually inspect and choose the best in regards to performance, stability etc.

There are a few things you could do to speed this process up, for example:

• Monitor your simulation, and at the first sight of crash or unwanted behavior abort. Set the cost function for this X to something really high.
• Reduce your feasible region if you know you can do this without risking missing the best X.
• In step 1, you could normally distribute your random value around some area that you "know" is better.

I don't know if there is a name for this "optimization-method", but it works really well for optimization problems where your cost function is really really noisy and the global minimum might be very isolated. It is also good if you have a good understanding of the problem and possible solutions.

Hope this helps someone.

[Ronald Jäpel]

> I don't know if there is a name for this "optimization-method"

There is: it's a genetic algorithm, without a recombination step. But you have the random initialization, evaluation, selection, mutation, and subsequent cycles of evaluation, selection, and mutation.

And I'd agree that a genetic algorithm or a particle swarm optimization might be Mathias' best bets.