Should we always search for the global minima in our optimization problem?

I am trying to fit a custom equation to a series of data. When I change the startpoints the obtained fitting parameters and the fitted curve to data changes. I am wondering should we always search for the global minima in our fitting (optimization) problem by using e.g. multistart or global search?

Thank you in advance!

Answer 1

[John D'Errico]

Yes. And, no. Amazing how the anwer is often, well, it depends...

You do want to find the true global min. Yes, that makes sense, as sort of a truism. But many problems are trivially solved without making the larger amount of effort to find a global min. Doing a global search takes more time. So do you ALWAYS want to waste time that need not be wasted? Of course not.

As well, in some cases, global solvers are not as good at zeroing into an accurate solution, whereas other tools will be rapidly convergent to the solution when they get near to it. So you may get a few less decimal places in the model parameters. And sometimes, those extra decimal places are really important.

It is often the case that merely having good starting values is sufficient to find the correct solution, without need for recourse to a global solver.

Looking at the converse, yes, a global solver can help. Sometimes. It makes things simpler for the novice. If you have no clue where to start a solver, a global solver typically just does not care.

A metaphor I often use for these questions is to think of the utilities in MATLAB, the various toolboxes and the tools in them, as if they were tools in your workshop. For example, in my shop, I have many screwdrivers, wrenches, hammers, saws. I know how to use all of them well, when to use one of the other. But supppose that tomorrow, XYZ comany introduces a magical tool that does everything for you. (They like to do that around the holidays.) So a tool that can turn any bolt, screw, cut any piece of wood for you, drive any nail. Not only that, but it is battery powered, with a lifetime battery!

What are the odds that the XYZ magic tool does its job only barely acceptably? Some of the time, it works nicely enough, but some of the times, it leaves a massive mess on your hands, destroying the part you are working on?

The point is, if you understand the tools in your workshop, if you understand the problem you are working on, then you will know which tool to use. You will not need to resort to the XYZ magic tool.

So understand the tools. Spend the time to learn how each optimizer works, what it does well, what it does poorly. What each one can do, and when to use it. Do the same time on the problem you want to solve. If you can, plot it. Look at how it works. What do the parameters mean? What are good starting values. PLOT YOUR DATA. Do your thinking in advance.

Of course, you don't need to do any of those things. But I will say that the person who wanders into my workshop and just starts grabbing random tools will probably soon find they are missing a hand, or at least some fingers. The same thing applies to the utter novice in MATLAB. That person may well find a global optimizer a good first choice, as it removes some of the need to understand the tools you are using. But I've seen as many novice MATLAB programmers having problems using the global optimizers as any other tool.

There is simply nothing better than understanding the tools you will use.

[Shaily_T]

Thanks for your nice explanation! Yeah, actually for me even when I use global solvers (multistart or global search) the answer is the same as local solvers which seems strange to me.

Could you please let me know if you are aware of any good source to go through the tools and undrestand them better?

Answer 2

[Matt J]

I am wondering should we always search for the global minima in our fitting (optimization) problem by using e.g. multistart or global search?

If when you say "we", you mean "everybody", then no. There are plenty of people who work with models for which it is not challenging to find the globally best fit without GlobalSearch. For example, polynomial and spline fitting problems do not have non-global minima, so it isn't something you have to worry about in scenarios like that.

However, your particular model may be unusually difficult and therefor may warrant a global optimizer if you are finding it challenging to identify a good initial start point. To be sure that your difficulties are not self-inflicted, however, it might be advisable to present a mathematical description (i.e., equations, not code) of the curve fitting problem you are facing. The community may then be able to recommend initialization strategies.

[Shaily_T]

Thanks for your response! I have already tried using multistart and globalsearch in my code but the obtained fitting parameters are the same as not using multistart and global search. Also the result of multistart and global search only changes with my startpoints. I have attached the picture of the equation I am trying to fit data to. I am trying to fit "h" in my equation to data. My x is "freq" and my y is "h" . r1 , r2 , c , Start are constants and a, sigma, dis, d0 are fitting parameters. d is indeed a series of 9 Gaussian functions. "Rn" is related to "d" through "kramers-Kronig" relations. So its value at each point is dependent on the value of d at all points. https://en.wikipedia.org/wiki/Kramers%E2%80%93Kronig_relations

Thank you in advance!

Answer 3

[Walter Roberson]

No!! Finding the "true vacuum" (global minima) energy state of the universe could be an utter disaster of the highest possible order!!! https://cosmosmagazine.com/science/physics/vacuum-decay-the-ultimate-catastrophe/?amp=1

Answer 4

[Sam Chak]

Hi @Shaily_T

For academic reasons, maybe a 'Yes' if your team want to demonstrate the novelty in the optimization problem that no one has done this before.

In most commercial industrial practices, then it's a 'No' because your team must to find the optimal solution in the operating region of interest only, so that the company can make cost-effective products at a profit in the desired specified time frame.

[Walter Roberson]

Suppose for example that you are exploring a chemical production process. Suppose that there is an energy barrier and probability of overcoming it is temperature dependent. But temperature is always a distribution, and if you simulate long enough, you might happen to simulate a one in a trillion particle that has enough simulated energy to cross the barrier. Is that one in a trillion pathway realistic or meaningful for your production? (It might be. With one mole being more than 1e23, one in 1e12 could still give 1e11 output, and in some cases it might be worth it... but more often you would increase the temperature to get more output.)

[Shaily_T]

Hi @Sam Chak and @Walter Roberson

Thanks for your response! In my academic project, I have some series of data taken at different frequencies, and I have a model that we want to demonstrate it explains the experimental data. We aim to fit our model to data and obtain the fitting parameters. And then using the obtained fitting parameters to calculate a physical quantity by another equation in our model and compare it with the obtained experimental result for that quantity. Should I check for the global optima in this case in my fitting problem? Or if I find a result and it works well, it is okay.

What made me think of the global optima is when I use the "levenberg-Marquardt" algorithm in my fit, the result of my fit and the obtained fitting parameters are dependent on the start points I used.

Thank you inadvance!

[Walter Roberson]

Your d is the sum of Gaussians. It is difficult to fit such a sum, and the results you get often depend strongly on the starting point.

Each Gaussian requires 4 parameters to fit, but it turns out that once you have two of the parameters for each Gaussian, it is possible to recover the remaining parameters through a linear process. I have long forgotten the details. I doubt I still have the source code for that purpose.

[Shaily_T]

Thanks for your response. Yes, the answer dependes on the starting points especially if I use "LevenBerg-Marquardt" algorithm. For trust region it also dependes on the starting points but the dependent is less compared to "levenberg-Marquardt".

Could you please elaborate more on the linear process you mentioned? or is there a link to know more about it or a source codes for that purpose?

[Matt J]

Could you please elaborate more on the linear process you mentioned? or is there a link to know more about it or a source codes for that purpose?

If you knew the parameters b_i and c_i in the sum-of-Gaussians model,

then y is a linear function of the remaining unknowns a_i. You could obtain the a_i by solving a linear system.

This means in effect, that a_i can be written as a function of b_i and c_i and therefore eliminated as unknowns from your model. With the a_i eliminated, you do not need to provide initial guesses for them. You only need to provided guesses for b_i and c_i.

[Torsten]

This means in effect, that a_i can be written as a function of b_i and c_i and therefore eliminated as unknowns from your model.

The a_i still depend on x - thus cannot be eliminated from the model.

[Matt J]

The x are constant data. For every pair (x(j),y(j)) we get an equation in the a_i.

[Torsten]

So you mean - given b_i and c_i in each iteration during the nonlinear fitting process - you solve for the optimal a_i (by solving the usual overdetermined linear system of equations) and return the respective residual to the solver so that the a_i don't need to be solved for as further unknowns ? That's clever, but maybe hinders convergence because of the decoupling.

[Matt J]

It is the basis of John's fminspleas routine,

https://www.mathworks.com/matlabcentral/fileexchange/10093-fminspleas

Reducing the number of unknowns generally aids convergence. What maybe tricky though is differentiability. The a_i will not necessarily be a differentiable function of (b_i,c_i) which could impact derivative-based solvers like lsqcurvefit.

[Walter Roberson]

A Gaussian can be characterized by its position, its Full Width Half Height, its magnitude, and its phase. I no longer recall which two parameters can be recovered, but I do recall that position was not one of them. My brain is suggesting it was magnitude and phase that were recoverable.

We side-stepped differentiability by using Levenberg-Marquart, which by itself does not assume differentiability.

All this was on the order of 25 years ago, and we were writing in IDL (and possibly C).

[Shaily_T]

Thanks for the clarification! What if I only know b in my case? I cannot use this linear process. Is that correct?

Also, in my case I have assumed a_i , b_i and c_i are the same for all Gaussians. So, I guess it should make it easier.

[Torsten]

Also, in my case I have assumed a_i , b_i and c_i are the same for all Gaussians. So, I guess it should make it easier.

But then you only have one Gaussian, not a sum of them. Thus you don't need to sum up to 9, but take only the first summand.

[Matt J]

We side-stepped differentiability by using Levenberg-Marquart, which by itself does not assume differentiability.

LM does require differentiability. Maybe it was Nelder-Meade?

[Matt J]

Thanks for the clarification! What if I only know b in my case? I cannot use this linear process. Is that correct?

You can use it even if you know neither b nor c. Recall,

This means in effect, that a_i can be written as a function of b_i and c_i and therefore eliminated as unknowns from your model. With the a_i eliminated, you do not need to provide initial guesses for them. You only need to provided guesses for b_i and c_i.

Also, in my case I have assumed a_i , b_i and c_i are the same for all Gaussians. So, I guess it should make it easier.

That seems unlikely to me. It would mean you only have 1 Gaussian.

[Walter Roberson]

It might perhaps make sense in some situations to have a sum of Gaussian that each have the same a and c, but different b (b being the center position.)

If that is your situation, then would the center positions b happen to be at regular intervals? Known interval?

[Shaily_T]

Yes, sorry I meant only a and c are assumed to be the same but b is different. The center positions b are happen to be at regular intervals. And the distance between them is a fitting parameter (also assumed to be the same between all Gaussians).