How to know if a minimum found with Global Search is actually the Global minimum?

I try to find a global minimum with fmincon() in a GlobalSearch. I gave it a maximum runtime of 30 minutes. The solver ended long before that with the following message:

gs = GlobalSearch('MaxTime',1800);    %
[global_min,fg,exitflag,output,solutions] = run(gs,problem)


GlobalSearch stopped because it analyzed all the trial points.

3 out of 19 local solver runs converged with a positive local solver exit flag.
Elapsed time is 507.457135 seconds.

exitflag = 2

I know that these 3 found solutions are local minima, but is the "most optimal" of those minima, the one saved in 'global_min' actually the global minimum? How can I find out if it is? The documentation for GlobalSearch() does not seem to cover it.

[Stephen23]

"How can I find out if it is?"

Write out all of the (possibly infinite) points of your data space (use grid paper**) and calculate the function by hand for every datum point. Then you will know if the solution found by a numeric optimzation algorithm is the actual minimum or not.

"The documentation for GlobalSearch() does not seem to cover it."

It would be quite surprising to many people in quite a few academic disciplines, if the MATLAB documentation gave the general solution to a problem that has no general solution:

https://www.mathworks.com/matlabcentral/answers/353498-global-minimum-for-non-linear-constrained#answer_278739

https://www.mathworks.com/matlabcentral/answers/516484-is-there-a-way-to-find-a-global-minimum-using-genetic-algorithm#answer_424879

https://www.mathworks.com/matlabcentral/answers/58800-how-can-the-global-minimum-be-got-using-optimization-toolbox#answer_71163

You might be able to solve this problem using quantum computing, but I am not an expert on this topic.

** or whatever the higher-dimension equivalent is.

[e_frog]

"calculate the function by hand"

i hope this is sarcasm, because I definetly can not calculate my problem by hand. It would take centuries. :)

Does this answer imply, that you can only find a global minimum with the symbolic toolbox? If yes, then I cant use it, because I am calculating differential equation systems of a higher order.

Is at least my assumption correct, that the minimum saved in 'global_min' is the 'most optimal' minimum regardless of it being a global minimum or not?

[Bjorn Gustavsson]

You have to think about optimization-problems as a generalization of finding the topographically lowest point in some region or the corresponding higher-dimensional expansions, as far as I understand this. The optimization-function does its best, to find this point, using some algorithm, typically there are some underlying assumptions about smoothness, or even smoothness of the gradients, using some of any number of clever algorithms. Regardless of which algorithm that is used it is impossible to exclude the possibility that there is a close to infinitely deep hole somewhere in this region, and this hole might be infinitesimally narrow too, without necessarily violating the smoothness of the function, imagine a 2 (or N) dimensional Gaussian that is very narrow and deep. No algorithm can guarantee that such a narrow minima is found.

[Stephen23]

"Does this answer imply, that you can only find a global minimum with the symbolic toolbox?"

I don't see how symbolic mathematics can provide a general solution, if the function itself is provided as a black-box.

Of course if the function or algorithm is known then this knowledge could potentially be used numerically or algebraically or in some other way to reduce the task complexity or perhaps even generate a general solution. Symbolic mathematics might be one tool that could be used here.

"...that the minimum saved in 'global_min' is the 'most optimal' minimum regardless of it being a global minimum or not?"

The run documentation

https://www.mathworks.com/help/gads/globalsearch.run.html#d122e55853

describes its first output as "Best point found, returned as a real array. The best point is the one with lowest objective function value."

[John D'Errico]

What do you mean by this: "Is at least my assumption correct, that the minimum saved in 'global_min' is the 'most optimal' minimum regardless of it being a global minimum or not?"

Sorry, but "most optimal" is a bit like being semi-pregnant. The min found is either the global min, or it is not. Most optimal makes no mathematical sense.

As I explain in my answer though, there is NO assurance that the min found will be the true global min. But again, that is IMPOSSIBLE to know on some fully general function.

[e_frog]

yes you are right. My wording for that is strange.

Stephen also already answered this question, by citing the run documentation:

"The run documentation

https://www.mathworks.com/help/gads/globalsearch.run.html#d122e55853

describes its first output as "Best point found, returned as a real array. The best point is the one with lowest objective function value.""

I must have not seen this in the run documentation.

Thank you all for your fast answers. I really would like to accept them all!

[John D'Errico]

Bjorn & Stephen: Suppose I had the power to "move" your responses into answers? Would you not have liked that? Both of your comments were quite good and to the point, and were certinly good enough to be answers. But you used comments for a reason.

[Stephen23]

@John D'Errico: I sense a meta-discussion related to recent communications we have had with TMW...

Yes, I used comments for a reason.

But when I think about it now, these are mostly rather ephemeral, personal reasons which are not particularly important from an objective view of this thread: because I happen to believe something about information presentation, about communication, about curent and future readers, etc., i.e. due to my views and beliefs about people and this forum, which are quite possibly incorrect. I can certainly conceive that someone else might view the structure of information on this thread in a different way to me, based on some different knowledge and beliefs than mine. Thus from an objective perspective, moving my comment to an answer could make sense. Who am I to disagree?

Perhaps the strongest argument against moving a comment to an answer is simply one of politeness: i.e. acknowledging that the original author had their own reason for making a comment rather than an answer.

[John D'Errico]

How could you possibly have guessed? :) Thank you for your thoughts.

I do agree, that sometimes I will post a comment that is probably quasi-adequate as an answer, but put it in a comment for a variety of reasons. When I do, the odds are good that my comment is not as well thought out or as complete as it would be if I really wanted it to be an answer in the first place. In that case, if someone else were to arbitrarily move it into an answer, then I will probably be unhappy. It might force me to spend the extra time I did not wish to spend to upgrade my now answer.

Regardless, I think you are correct. Politeness suggests the best solution is to just ask the commentor to move their comment into an answer.

[e_frog]

Was I unpolite to not ask to switch your comments to answers? If thats the case I am sorry!

[Bjorn Gustavsson]

@e_frog: Not to worry, you only displayed the not unusual "out of class disappointment of meeting the reality of not nice example-problems" - I've stomped around the office and our lab crying about how unfair universe is that it has given me problems that aren't nicely solveable, I've even used bad language on occasion...

@John D'Errico, that would've been perfectly OK, I didn't know I would make a good enough contribution when I started typing, and when I finished I didn't bother shifting it.

[Stephen23]

@e_frog: your question is a good one and your response to the answers/comments has been exemplary.

For your information, the last few comments are related to a proposed change to this forum, which some regular users are contemplating how it would be used effectively and under what circumstances. So really quite a meta-discussion.

Sorry for hijacking your thread!

[e_frog]

@Stephen Cobeldick no problem at all!

Answer 1

[John D'Errico]

Bjorn and Stephen should be encouraged to make their comments into Answers. But let me expand on what they have both said.

The point is it is impossible to ensure a numerical solver on a fully general nonlinear optimization problem (a complete black box) will find the global solution. This is because that objective may always contain a local minimum that is essentally a delta function, a virtually infinitely narrow hole. Even if the function is technically fully differentiable, such an effective numerical singularity will make any solver fail almost 100% of the time to find the true global solution.

Can you succeed in general with the symbolic toolbox? NO! There is not even any assurance a symbolic solver will work, because that problem reduces to finding all roots of a general nonlinear function. Again, this is impossible on almost all such nasty functions you will throw at it. And you have told us nothing about your problem, except that it is nasty.

The point is, you can WANT a solver to always give a global minimum, but if wishes were horses, beggars would ride.

The best you can do with a deterministic tool like fmincon is to use good starting guesses, or failing that, to use a multi-start method, with many start points. That INCREASES the probability you will find a solution. The same thing applies with any "global search" tool. Give it as good a chance as you can of finding its way into the basin of attraction of the global minimizer. That means you need to have a well sampled search space. Anyway, I said PROBABILITY above. I meant that. At best, you can try to improve the probability you will succeed, driving that probability closer to 1.

With high dimensional problems, things go to hell fast. Strong samplings of high dimensional search spaces becomes nearly impossible. The curse of dimensionality makes things really bad, and really fast. Can you improve things there? Sometimes...

The point is that just as good starting values are a huge benefit for any deterministic downhill solver, to get into the basin of attraction of the global min, you need to constrain the solver as highly as possible. If you know something about the solution, then that information needs to go into bound or inequality constraints of some form. Such constraint sets can make an ill-posed problem into a well-posed one.

[Steven Lord]

As a concrete example of what John said, how would you distinguish between these two functions based solely on evaluating them on a set of points? Assume you couldn't see the if statement in fun2.

function z = fun1(xy)
z = peaks(xy(1), xy(2));
end

function z = fun2(xy)
z = peaks(xy(1), xy(2));
if xy(1) == pi+exp(1) && xy(2) = -999
    z = -realmax;
end
end

Unless your minimizer evaluates fun2 at EXACTLY (pi+exp(1), -999) it's not going to see that "pit".

It would be like trying to find the lowest location on land on Earth by starting at many, many points on the surface of the planet. If all of your points were in the United States you'll likely find yourself in Death Valley (85 m below sea level) or maybe in Argentina (105 m below sea level.) You may find the Dead Sea (430 m below sea level.) But if we say the bottom of the Kola Superdeep Borehole counts, your search is extremely unlikely to find it.

[e_frog]

That is a great and illustrative example!

[e_frog]

I actually have a follow-up question. If it is not okay to ask here, I would open a new thread.

If i gave the global-search 30 minutes for finding a global minimum and it ends after 8 minutes with the message

GlobalSearch stopped because it analyzed all the trial points.

3 out of 19 local solver runs converged with a positive local solver exit flag.
Elapsed time is 507.457135 seconds.

1) does it mean that Globalsearh only tries out 19 "combinations" of variables in fmincon (my variables would suggest 10000x more possible combintions)

2) or does it try out all possible combinations of variables and 19 of those possibly could have been a minimum but only 3 of those were a local minimum

3) or does globalsearch somehow has a fix number of random variable combinations in fmincon that it tries out before ending?

How would I increase the number of trial points?

[Walter Roberson]

GlobalSearch ran fmincon on 19 starting points. Each of those might have evaluated the function a number of times. 16 of the 19 starting points returned saying "I could not find any minima, for whatever reason". 3 of the 19 starting points returned saying "I found something in the time I spend".

GlobalSearch considers 1000 candidate points by default, but it has algorithms for filtering out points as it goes, based upon the results of runs, so there can end up being many fewer fmincon runs. See https://www.mathworks.com/help/gads/how-globalsearch-and-multistart-work.html#bsc9eec

[e_frog]

Thank you!