CODEWITHSUNDEEP
c#mathoptimizationnonlinear-functionslevenberg-marquardt
Jkh2
Jkh2

Reputation: 1030

Optimise parameters in a set of non-linear equations simultaneously

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?

Upvotes: 3

Views: 1565

Answers (1)

Ron Kaminsky
Ron Kaminsky

Reputation: 294

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).

Upvotes: 1

Related Questions