3

I have a large number of equations (n) with a large number of unknowns (m) where m is larger than n. I am trying to find the values of m using the n equations and a large set of observed values.

I have looked at some implementations of Levenberg-Marquardt in C# but I couldn't find any that solve more than 1 equation. For instance, I looked at http://kniaz.net/software/LMA.aspx and it seems to be what I want except that it only takes a single equation as a parameter, I want to solve for a number of equations at the same time. Similarly this package: http://www.alglib.net/ contains a good implementation of LM but only for a single equation.

I was wondering if there are any good implementations in C# or that I can use with my C# code that can do this? It will be costly to attempt to work out the first order differentials of my equations as well so I am hoping to be able to use small finite differences to approximate them.

Furthermore is there any good and easy to understand explanation of how LM works and how to implement it? I have tried reading through some maths textbooks in order to implement it myself but I am pretty clueless at maths so most of the explanation is lost on me.

edit:

More details of my problem:

1) The equations are formed dynamically and can change with each running of my problem

2) I have no good guess for the starting parameters. I am planning to run it multiple times with randomised starting parameters in order to find the global minimum.

Edit 2:

One more question, I am reading this paper: http://ananth.in/docs/lmtut.pdf and I saw the following under section 2:

x = (x1; x2 ... xn) is a vector, and each rj is a function from ℜn to ℜ. The rj are referred to as a residuals and it is assumed that m >= n.

Does that mean that LM does not work if I have more parameters than functions? For instance, if I want to solve A and B for the function:

Y = AX + B

It won't be possible due to the fact that my parameter vector is of size 2 (A and B) and my function count is 1?

Jkh2
  • 1,010
  • 1
  • 13
  • 25
  • Late here, but researching the same thing, I came across [this](http://www.trentfguidry.net/post/2011/12/10/Implementing-Levenberg-Marquardt-algorithm-nonlinear-least-squares-regression-multiple-weighted-simultaneous-functions-in-C-sharp.aspx) recently, just code on some guys blog though, so no guarantees... – Benjol May 29 '12 at 12:00

1 Answers1

1

The Levenberg-Marquardt algorithm can handle your problem; however, I do not find an implementation in C# which implements that case [UPDATE: see edit below for details of how to get alglib.net to do what you want]. MINPACK does have entry points for that case (LMDIF1 or LMDIF, if, as you stated, you wish to approximate derivatives using differences). You might try automatically translating the C/C++ version of MINPACK using tools listed at a previous question on StackOverflow.

As for your question in "Edit 2": "Does that mean that LM does not work if I have more parameters than functions?", the answer is: no, you are wrong. "m" in the paper at that point is actually, in your case, equal to the number of equations you have, multiplied by the number of data points you have (assuming what you mean by "observed value" is a value for the difference between the right-hand side and left-hand side of every equation). In other words, the r-sub-i functions, which he talks about there, are exactly those equation disparities (RHS - LHS).

Important edit: now I see that the second package you found, alglib.net, will do what you want (but note that it is only available for free under GPL). Since you don't want to provide derivatives, you should use the "V" scheme, where, assuming you have n equations and k observed values at the parameters , the f vector has n*k elements where

f[i + j*n] = (RHS_of_equation[i](data_point[j]) - LHS_of_equation[i](data_point[j]))

(i and j start at 0, of course).

Community
  • 1
  • 1
Ron Kaminsky
  • 294
  • 3
  • 10
  • Thanks for the reply, I am not too sure where the alglib.net V function is however. I can only find a F, FG and FGH option for the non-linear fitting with observed points. http://www.alglib.net/interpolation/leastsquares.php#header20, am I looking at the wrong function? – Jkh2 Feb 12 '12 at 02:01
  • Look at the example code at URL http://www.alglib.net/translator/man/manual.csharp.html#example_minlm_d_v ... but change function1_fvec to match my explanation. – Ron Kaminsky Feb 12 '12 at 02:11
  • Ah great, I think I understand it now. Just to make sure, say if I have one of my equations as y = 2x + c, where y is my observed point, x is a known value and c is the unknown. It would be f[0] = 2x + c - y? Thanks for all your help so far btw, its been invaluable :) – Jkh2 Feb 12 '12 at 02:22
  • "It would be f[0] = 2x + c - y?" Yes, more or less, except that you would have _multiple_ f's for this one equation --- one for _each_ observed point. Similarly, for each observed point you would have _multiple_ f's --- one for _each_ equation. – Ron Kaminsky Feb 12 '12 at 16:13
  • Great, thanks for your response, I am using alglib minlm now and it seems to work :) – Jkh2 Feb 12 '12 at 21:25
  • C/C++ version of minpack was already automatically translated from FORTRAN (complete with `goto`), I dread to think what the further translation into C# would look like! – Benjol May 29 '12 at 12:07