Why doesn't Multistart converge to the optimal solution?

I'm using Multistart-fmincon-interior points from the Global Optimization Toolbox to find the optimal solution of my objective function. There are two variables and one nonlinear constraint. The constraint is not directly linked to the variables, but ultimately depends on their values through a series of function calls. The model fails to find the optimal solution even after specifying 50 start points for Multistart, which is fairly high considering there are only two variables. I know that the solution is not the global optimum because I can fix my variables and obtain more optimal solutions that still satisfy the constraints.

I have tried to amplify the constraint value and modify its tolerence, I've also increased the finite difference step size in fmnicon, but to no avail.

Am I missing something?

What are the methods that ensure the optimal solution is found other than increasing the number of start points?

[Ameer Hamza]

Can you show your code? How did you call the multistart solver? Maybe, there is some issue with the code, but it might be the case that the multi-start did not converge for your optimization problem. The performance of the optimization algorithm depends heavily on the initial point. The advantage of Multistart is that it intelligently tries different initial points. But if the initial point you specified is far from the optimal solution, then there is not much that Multistart can do to improve. Therefore, one of the most important things is to specify a good initial point. Maybe, try to analyze your problem and see if there is something you can do to get a guess of the optimal value and use that guess as the initial point.

Alternatively, you can try functions from the global optimization toolbox, which does not require any starting point at all. For example, ga(), particleswarm(), and patternsearch().

[Stephen23]

"What are the methods that ensure the optimal solution is found..."

None.

There is no such method that "ensures" that the optimal solution is found.

If there were such methods everyone would be using them. But instead everyone is scrambling around inventing new solver algorithms based on the behavior of some animal they were particularly fond of when they were children.

None of which "ensure" an optimal solution (which is likely impossible, in the general case).

[John D'Errico]

I have invented the duckbill platypus method. It wanders around, and it likes the water, whch is good. Not very intelligent. Sometimes it lays an egg. But it can be cute and fuzzy.

Answer 1

[John D'Errico]

Sadly, there is NO method that can absolutely, positively insure the optimal solution is found. No matter how hard you try, I can construct a problem that will fail almost always.

Tools like multi-start are an ATTEMPT to reduce the probability of failure. They work some of the time. But they are not 100%. And nothing you do, beyond some extreme things where you might restrict the derivatives of the function in question to not be too extreme, nothing will save you from failure at least some of the time.

A comparison I like to make is to imagine a solver as a blind person, set down on the surface of the earth. Give them only a cane, and an altimeter. Their task is to find the point of lowest elevation. (I hope you gave them an altimeter that works underwater, and some scuba gear.) All they can do is to walk downhill in some way, based on input from their cane and their memory of where they have looked already.

In those circumstances, depending on where you initially set them down to start the search, what will probably happen? Will they get stuck in some valley? Perhaps in the bottom of some lake or oceanic trench? What are the odds they will find themselves to the deepest trench in the middle of the Pacific ocean? Instead, odds are, your poor blind friend will get stuck in a local minimum, perhaps in the Dead Sea, or just in some farm pond out in the boondocks. I did say to give him scuba gear! Most low spots are probably wet places.

Multi-start works by setting him down in random locations, in MANY local start points. Hopefully at least one of them will get this fellow to a happy location. More start points increases the odds of that event.

But if the deepest, lowest altitude location just happens to be at the bottom of a 25 mile deep drill hole, that worse, is drilled into the top of the highest mountain on Earth, then the odds are REALLY poor you will find it by this method. It does not matter how may places you start him out. Unless you start the search directly inside the drill hole, you will have the guy start walking downhill, AWAY from the solution. (I really feel bad for this guy, but we will pay him quite well for the service. Geez, try not to set him down in New York City at rush hour! I will tell you that no blind people were harmed in this thought experiment.)

So, what are the methods you can use? INCREASE THE NUMBER OF START POINTS. That is really your only viable choice, at least on the multi-start/fmincon side. Changing the finite difference will not help, in fact, it may hurt you. And cranking down on the convergence tolerance will not help either. Suppose the blind guy ends up in the Dead Sea? Will insisting he look for the lowest spot VERY carefully help any? Will that possibly get him to the Marianas trench in the Pacific? Of course not. He will just keep looking in the depths of that local depression, trying to reduce the altitude by another millimeter. Remember, he is trying to walk himself downhill. Temporarily walking uphill is not possible with fmincon.

You may decide to try different optimizers. Stochastic solvers like GA, etc., can sometimes work. They have some good and some bad attributes. A good aspect is they can effectively quantum tunnel out of some local depressions (that is, temporarily walk uphill.) A bad aspect is they often take more function evals to get to a solution, and they converge more slowly when they get near the solution. But still, if the global solution is inside a deep hole dug into the top of a high mountain, you will fail unless you get very, very lucky.

As I said, nothing you can do will insure success. All you can do is reduce the odds of failure. (As I said, if you use symbolic methods that are designed to limit the derivatives of your unknown function, then you can have some more success, but that requires a huge assumption about the objective function properties. And since optimizers are NOT symbolic tools, that option is out.)