How to find a global minimum using optimization in Matlab?

Question

I'm using the optimization toolbox function FMINSEARCH to find the minumum of a funtion through ajustments in a vector of four variables. It converges well but, depending on the initial condition, I achieve different solutions. Basically, the optimization proscess is trapped in a local minimum.

Any tips on how to "jump" the local minimums and search for the global one? Shall I use any other optimization function?

Thank you for your help...

Answer 1

DrMatt has great stuff.

You could wire fminbnd into a conjugate-gradient search.  Its an algorithm with quadratic convergence.

You could use multi-grid methods.

I guess the question nearly asks itself: what do you know about the function you are trying to optimize?  What is the function?  What are the knowns?  What are the criteria?

Answer 2

There is no way to ensure that you've found the global minimum. Matlab tries a few tricks to converge properly, but in the end the algorithms are subject to initial conditions, especially when the cost surface is complex.

One strategy is 'random restart', in which you sample the parameter space in a reasonable way and do a series of optimizations; each optimization starts with the initial conditions represented by a particular sample. For instance, if you were trying to find the global optimum of a function of a single variable that ranges from 0 to 1, then you could choose 10 samples in the interval [0,1] and run the optimization 10 times, starting at each sample.

Another strategy (though it can be computationally costly) is simulated annealing:

http://en.wikipedia.org/wiki/Simulated_a...

It's fairly easy to implement as an outer loop and is designed to find global optima, at least in theory. Some Matlab code here:

http://www.mathworks.com/matlabcentral/f...

This may work well, depending on your particular problem.