Thread Subject:

Large scale nonlinear unconstrained optimization method that avoids saving large matrices

Hello,

I have a system of nonlinear equations of size 500*3000 (approximately). The problem can be formulated as a nonlinear least squares problem. I have tried

- lsqnonlin, large scale, mostly with Levenberg-Marquardt (LM) option, suggested by lsqnonlin function, since the system is underdetermined.

- I have also tried this implementation of Levenberg-Marquardt.
http://www.mathworks.com/matlabcentral/fileexchange/17534-lmfnlsq-solution-of-nonlinear-least-squares

Both of these programs give good results, when the problem is not very big. However, they are not useful when I have a system of size 500*3000, for example. The Jacobian of my particular problem is not very sparse (but still not very bad), but using LM, since we need to compute J'.J, we get fill-in and the matrix becomes very dense and hence we face memory problems.

Could anyone suggest a large scale nonlinear unconstrained optimization method which does not require saving large matrices?

I would appreciate your help.
 

I included the wrong link. Here is the program I used:

http://www.mathworks.com/matlabcentral/fileexchange/16063-lmfsolve-m-levenberg-marquardt-fletcher-algorithm-for-nonlinear-least-squares-problems

"Nargol" wrote in message <igl12g$54o$1@fred.mathworks.com>...

> The Jacobian of my particular problem is not very sparse (but still not very bad), but using LM, since we need to compute J'.J, we get fill-in and the matrix becomes very dense and hence we face memory problems.

No you don't necessary need to compute J'*J: Many time J'*J is written in book to in order indicate solving a linearized normal system, which can be carried out with "\" operator.

For example take a look of my code in this thread:

http://www.mathworks.com/matlabcentral/newsreader/view_thread/281583#744680

Bruno

"Nargol" wrote in message <igl12g$54o$1@fred.mathworks.com>...
>
> Both of these programs give good results, when the problem is not very big. However, they are not useful when I have a system of size 500*3000, for example. The Jacobian of my particular problem is not very sparse (but still not very bad), but using LM, since we need to compute J'.J, we get fill-in and the matrix becomes very dense and hence we face memory problems.
========

So your J'*J is a dense 3000x3000 matrix ? That doesn't seem large enough to cause memory problems, even on computers from 5 years ago...

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <igl2l4$h12$1@fred.mathworks.com>...
> "Nargol" wrote in message <igl12g$54o$1@fred.mathworks.com>...
>
> > The Jacobian of my particular problem is not very sparse (but still not very bad), but using LM, since we need to compute J'.J, we get fill-in and the matrix becomes very dense and hence we face memory problems.
>
> No you don't necessary need to compute J'*J: Many time J'*J is written in book to in order indicate solving a linearized normal system, which can be carried out with "\" operator.
>
> For example take a look of my code in this thread:
>
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/281583#744680
>
> Bruno

Thanks Bruno for the code. I will try it. Hope it works this time.

"Matt J" wrote in message <igl9f5$bcd$1@fred.mathworks.com>...
> "Nargol" wrote in message <igl12g$54o$1@fred.mathworks.com>...
> >
> > Both of these programs give good results, when the problem is not very big. However, they are not useful when I have a system of size 500*3000, for example. The Jacobian of my particular problem is not very sparse (but still not very bad), but using LM, since we need to compute J'.J, we get fill-in and the matrix becomes very dense and hence we face memory problems.
> ========
>
> So your J'*J is a dense 3000x3000 matrix ? That doesn't seem large enough to cause memory problems, even on computers from 5 years ago...



Oh, thanks for pointing that out. I had missed a zero. It is about 30000*30000.