Message Boards Message Boards

0
|
6191 Views
|
16 Replies
|
1 Total Likes
View groups...
Share
Share this post:

Use the LevenbergMarquardt method with FindFit?

Posted 6 years ago

I would like to use the LevenbergMarquardt method with FindFit, or other methods, and cannot find detailed documentation on how to use LevenbergMarquardt in Mathematica. The same is true for all optimization commands. I am surprised I can't find any published/online documentation. Are there any resources beyond the basic information about optimization and curve fitting? That does not help very much. Thank you.

POSTED BY: pantelidis
16 Replies

It's the default method in NMinimize. Rewrite your fitting problem as an optimization problem and use NMinimize. This is usually done by minimizing the sum of the squares of the error terms.

POSTED BY: Frank Kampas

LevenbergMarquardt is not the default method for NMinimize. I'm not sure, but it might be default for FindMinimum when input is an explicit sum of squares.

POSTED BY: Daniel Lichtblau

What is the default method for NMinimize?

POSTED BY: Frank Kampas

I don't recall for certain but I am pretty sure it is either "NelderMead" or "DifferentialEvolution". Possibly there is even a heuristic to choose between those two. This is after preprocessing determines a general approach is required, e.g. problem is nonlinear or readily converted to an LP.

POSTED BY: Daniel Lichtblau

It's not DifferentialEvolution. That method generally gives better (but slower) results than the default.

POSTED BY: Frank Kampas

It is usually "NelderMead". But there are situations for which it is a mesh search (if dealing with explicit regions) or "DifferentialEvolution" e.g. if there are integer-valued variables or the objective is not an explicitly numeric function.

POSTED BY: Daniel Lichtblau

It would be useful to have someway of knowing what method was used, to avoid having to rerun it when trying to get a better result.

POSTED BY: Frank Kampas

It can perhaps be discerned from a tandem of StepMonitor and EvaluationMonitor output, say by sowing or printing how many evaluations were done in a given step. Bear in mind that a number of things could happen with the Automatic setting, that might help to disguise the underlying method.

(1) It could decide it was in trouble (e.g. failing to meet constraints) and switch.

(2) Preprocessing might change the problem (e.g. solving linear equality constraints to remove some variables).

(3) Postprocessing, if not specifically prevented, might change the method to a local one.

I might be missing some possibilities.

POSTED BY: Daniel Lichtblau

Ok, how about Method -> All which runs all the methods and tells you which result came from which method?

POSTED BY: Frank Kampas
Posted 6 years ago

Thank you Frank and Daniel. May I ask a few more concrete questions:

  1. I found an example with the following method within FindFit: ...Method -> {"LevenbergMarquardt", "StepControl" -> {"TrustRegion", "StartingScaledStepSize" -> .01, "MaxScaledStepSize" -> 0.1, "AcceptableStepRatio" -> 0.1}}...

If I understood the exact meaning of StartingScaledStepSize, MaxScaledStepSize, and AcceptableStepRatio, maybe i could try different values to accelerate the L-M method for the problem at hand. I tried some and I only decelerate it, so again, maybe the default values are the best (I do not know what they are, I just don't set any values).

  1. I believe that Origin uses L-M. It looks as if it is far better than other common curve-fitting methods for most problems. Is that true?

  2. If I take the global minimization route for my problem through using NMinimize, I wonder which method of NMinimize is generally the most robust. Also if I use PostProcess->FindMinimum with an NMinimize method, does this mean that FindMinimum kicks in as well?

Many Thanks.

Leo

POSTED BY: pantelidis

I do not know the answers to most of these but I'll comment on what I can.

From what little I recall of Levenberg-Marquardt, steps in a Newton (I believe) direction are either accepted or rejected based on objective function behavior. I would guess the ratio parameter is involved in that determination. Is L-M best for curve fitting? I would have to guess it depends on the objective function. It is really a method for explicit sum-of-squares formulations and often works quite well for those. But that does not equate to being always best-in-class.

For NMinimize, our experience is that Method->"DifferentialEvolution" tends to be slow but often gives best results. But bear in mind "often"!="always".

The post-process step will use FindMinimum in an effort to polish the result found by the main step, whatever method was used. This often helps insofar as the main methods are better suited for putting one in the right ballpark, whereas the local FindMinimum methods are better for fast convergence once in the right ballpark. That said, once in a while the post-process step will actually deliver a significant improvement when it manages to find a region the global main method in play had missed.

POSTED BY: Daniel Lichtblau
Posted 6 years ago

Thank you, this certainly helps.

The source of much difficulty is that my model is defined through a slow-converging infinite series and there seems to be no sure-fire method to deal with something like this. I wonder if MathOptimizer could help. Is this package still current and how could one go about purchasing it and installing it?

As a sidenote, I am not sure why NSum within the definition of the model does not work with FindFit, NMinimize etc. whereas Sum does work. It seems that Nsum with Euler-McLaurin method is slower but works out better than Sum for slow-converging series.

POSTED BY: pantelidis

For numeric functions like NSum, you often have to hold evaluation until all parameters have numeric values:

BlockRandom@Block[{f, x, a},
  f[x_?NumericQ, a_?NumericQ] := NSum[(x - a)^n/n!, {n, Infinity}];
  SeedRandom[0];
  FindFit[Table[{t, E^t + RandomReal[0.001]}, {t, 0., 5.}],
   f[x, a],
   {a},
   {x}]
  ]
(*  {a -> -0.00916026}  *)

See also http://support.wolfram.com/kb/12502.

POSTED BY: Michael Rogers

In addition to the good suggestion by @MichaelRogers, I will mention that it is difficult to offer much assistance in the absence of a concrete example.

POSTED BY: Daniel Lichtblau

MathOptimizer is still available. However, I don't think it would help for your particular problem.

POSTED BY: Frank Kampas
Posted 6 years ago

Michael, thank you very much and sorry for my late reply. This is exactly it.
Thank you Frank and Daniel. Daniel, you are right. I am still in the middle of things but I will soon post some code as I am very interested in seeing how one could potentially speed up curve fitting and optimization when the model is a slow-converging infinite series. Using FindFit with LevenbergMarquardt is the only method that gives me any reasonable run times and so I will use it for now. Attempts to use Parallelize or Compile to speed up have failed but I may be doing things wrong so I will certainly post some code soon.

POSTED BY: pantelidis
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract