levenberg-mardquart algorithm in matlab

[ruslan]

hi ,
I am supposed to write matlab code to solve problem in LM algorithm. On net I couldnt find good documentation and or example about LM to understand it. briefly I need simple example to get understand algorithm for at least to know for what some varaibles is used there


any help will be appreciated

[Miroslav Balda]

Post by ruslan
hi ,
I am supposed to write matlab code to solve problem in LM algorithm. On net I couldnt find good documentation and or example about LM to understand it. briefly I need simple example to get understand algorithm for at least to know for what some varaibles is used there
any help will be appreciated

Hi,
Look at File Exchange, function LMFnlsq, Id. 17534.
Mira

[ruslan]

thanks for responce

I've checked those files. but I couldnt understand yet. by the way I have to implement LM (levenberg-mardquart) but not LMF(levenberg-mardquart-fletcher).

from wikipedia in http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm final equation is that

(J(T)*J + lambda*diag(D(T)*D))*delta = J(T) [y - f(beta)]

where J = jacobian , J(T) = transpose of jacobian , D=hessian.
for what cases should I use lambda, delta and beta and how to start for implementation and loop for iterations.

for this let me ask simple question f(x) = x*x - 5. and could you give me pseudo-code for this to solve it.

[Torsten Hennig]

Post by ruslan
hi ,
I am supposed to write matlab code to solve problem
in LM algorithm. On net I couldnt find good
documentation and or example about LM to understand
it. briefly I need simple example to get understand
algorithm for at least to know for what some
varaibles is used there
any help will be appreciated

Take a look at
Numerical Recipes in Fortran
or
Numerical Recipes in C

The LM - method is explained there for solving
nonlinear least-squares problems and code in the
corresponding language is given.

Best wishes
Torsten.

[ruslan]

ok, I've got that book, it seems very helpfull

thank you ;)

[ruslan]

hi, I still have problem with this algorithm. I want to find gloabl minimum point. I coded these codes. but still I cant solve problem. I can not evaluate function value, since I get nX1 matris not single value in the scope of while loop2. where p = *****. here I get a matrix, but I think I should get single value. I've looked some codes on net,but it seems very hard to understand from those codes.I know I miss something. any help pleaase ...

x = linspace(0,11,12)';
y = [12 10.5 9 6 4 3.5 3.2 2 1 2 4 7]';
order = 12;
coef = polyfit(x,y,order);

yy = polyval(coef,x);
%%% function is defined %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


iteration = 30;
mu = 0.01;
e = 0.01;

fnext = 0;
zz = ones(1,12) + 8;
z = zz';

list = [ 12 11 10 9 8 7 6 5 4 3 2 1 ];
d = (coef(1:12).*list);
k = 0;
loop1 = 1;
while loop1
k = k + 1;
fprev = polyval(coef,z);
xx = z';
jacobian = d*[(xx').^11 (xx').^10 (xx').^9 (xx').^8 (xx').^7 (xx').^6 (xx').^5 (xx').^4 (xx').^3 (xx').^2 (xx').^1 (xx').^0]';
loop2 = 1;
while loop2
p = -inv(jacobian'*jacobian + mu*eye(12))*jacobian'*e;
z = z + p;
fnext = polyval(coef,z);
if (fnext < fprev)
mu = mu / 10;
loop2 = 0;
else mu = mu*10;
z = z - p;
end
end
if (k == iteration)
loop1 = 0;
end
end

[Walter Roberson]

Post by ruslan
hi, I still have problem with this algorithm. I want to find gloabl minimum point.

You will have a problem no matter what you do. There is no *possible* deterministic
algorithm for reliably finding the global minimum of arbitrary infinite functions in
finite amounts of time (well, unless you can do something with quantum computing,
but even then it is sometimes argued that the amount of time required for that
involves imaginary numbers.)

(By the way, it is Levenberg-Marquardt, not Mardquart)

[Manu Raghavan]

Ruslan,

The termination condition, fprev < fnext, must be based on scalars, as you
pointed out. There is some inconsistency in your call to POLYVAL along these
lines.

As a start, you might want to compare your LM function against the built-in
MATLAB version, which should be visible if you have the Optimization
Toolbox:

edit( fullfile(matlabroot,
'toolbox\optim\optim\private\levenbergMarquardt.m') )

In the built-in LM solver, the terminating condition is predicated on
whether the sum of squares of the error term is reduced from iteration to
iteration:

if ~isempty(YDATA)
trialCostFun = trialCostFun - YDATA; % If fitting to data, compute
residuals
end
<snip>

trialSumSq = trialCostFun'*trialCostFun; % Scalar value


if trialSumSq < sumSq % Terminating condition

You might want to consider a terminating condition along these lines.

Best,

Manu Raghavan

Post by ruslan
hi, I still have problem with this algorithm. I want to find gloabl
minimum point. I coded these codes. but still I cant solve problem. I can
not evaluate function value, since I get nX1 matris not single value in
the scope of while loop2. where p = *****. here I get a matrix, but I
think I should get single value. I've looked some codes on net,but it
seems very hard to understand from those codes.I know I miss something.
any help pleaase ...
x = linspace(0,11,12)';
y = [12 10.5 9 6 4 3.5 3.2 2 1 2 4 7]';
order = 12;
coef = polyfit(x,y,order);
yy = polyval(coef,x);
%%% function is defined %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
iteration = 30;
mu = 0.01;
e = 0.01;
fnext = 0;
zz = ones(1,12) + 8;
z = zz';
list = [ 12 11 10 9 8 7 6 5 4 3 2 1 ];
d = (coef(1:12).*list);
k = 0;
loop1 = 1;
while loop1
k = k + 1;
fprev = polyval(coef,z);
xx = z';
jacobian = d*[(xx').^11 (xx').^10 (xx').^9 (xx').^8 (xx').^7 (xx').^6
(xx').^5 (xx').^4 (xx').^3 (xx').^2 (xx').^1 (xx').^0]';
loop2 = 1;
while loop2
p = -inv(jacobian'*jacobian + mu*eye(12))*jacobian'*e;
z = z + p;
fnext = polyval(coef,z);
if (fnext < fprev)
mu = mu / 10;
loop2 = 0;
else mu = mu*10;
z = z - p;
end
end
if (k == iteration)
loop1 = 0;
end
end