Which solver / Optimization algorithm is best to solve the function with multiple local minima.

I am trying to solve a 'Constrained Non-linear' objective function having 2 variables (Height and Thickness).

But as figure shows, function contains multiple local minima.

I have tried using all applicable solvers from MATLAB Optimization Toolbox. Also tried Hooke-Jeeves pattern search algorithm.

But calculated solution is always one of the local minima unless starting point / initial guess is given somewhere closer to the actual solution (Global Minimum).

Could you please suggest me any better solvers or optimization algorithms?

Thanks in advance. :)

Answer 1

[John D'Errico]

As Matt says, ga or multistart is an option. The idea is that no general optimizer will be good at this. They are too easily trapped in a local minimum. And you get into a local min that depends on where you start. What you need to do is find the BEST local min.

And that is the fundamental problem. You need an intelligent start point for any tool to work well, if it depends on the start point. The nice thing about multistart methods here is they will throw lots of start points out, and you hope that at least one of them is good. So they are somewhat dependent on luck, but you reduce the luck needed by taking more start points.

However, I'd find a completely different approach, were it my problem to solve. The picture you show clearly has a set of solutions that all lie strongly along a path in 2 dimensions. Is that a straight line? Or a curve? I cannot see. Regardless, I would sped just a few minutes to look at the equations of your surface. Is it obvious what the equation of that path is? Even if not, I may well be able to infer that that curve is just from the surface itself. Anyway I can do it, I would resolve that path that contains the set of local minima.

Having done that, then I have just reduced the TWO dimensional problem to effectively a ONE dimensional problem. Now just sample sufficiently many points along that path. Find the point that is minimal from the set of sampled points. Use THAT as your start point.

Essentially, the idea is to reduce the problem to a multistart optimization in ONE dimension. It is far more efficient to search in one dimension than in multiple dimensions.

I don't have your objective function, so I cannot show you how this would work.

[Aniket Kapse]

Thanks John.

The approach you proposed in the 3rd paragraph is right. The points joining all the local minima is a curve.

As you suggested, I used 1st variable 't' into a for loop and calculated minima at every thickness 't' using 'fminbnd' and then chose the optimum value i.e. Global minima.

Thanks for your suggestion. :)

Answer 2

[Matt J]

You could try ga or MultiStart.

[Aniket Kapse]

Thanks Matt. But I have already tried 'gamultiobj', 'ga' and 'MultiStart' as well. But the problem with ga and gamultiobj is a large number of iterations and their inconsistent answers.

Particleswarm seemed promising, but again, stochastic answers.

These optimization functions are taking more iterations than the regular branched for loops.

Anyways, thanks for your suggestion. :)

Answer 3

[Matt J]

But calculated solution is always one of the local minima unless starting point / initial guess is given somewhere closer to the actual solution (Global Minimum).

Why is that a problem? Since you only have two unknowns, an initial guess close to the global minimum is very easily found (as you have done above) by taking samples of the surface of the cost function

Answer 4

[Jason Climer]

I have found that the particle swarm optimizer is the best approach to problems with ugly surfaces like this one.