From: randy@aplcorejhuapl.edu (Randall C. Poe) Newsgroups: sci.math Subject: Re: Reference for Levernberg-Marquadt theory Date: 30 Jan 1995 17:32:12 GMT In article <3g8g10$12g@hippo.shef.ac.uk>, el3bpa@sunc.sheffield.ac.uk (B Amavasai) writes: |> I wonder if you could advise me. I'd like to know more |> about the Levernberg-Marquadt non-linear optimisation |> theory and would be glad if you could recommend me text |> which outlines the technique at all levels. |> I believe that's Levenberg-Marquardt. I think Marquardt's original paper appeared in a SIAM (Society for Industrial and Applied Mathematics) Journal somewhere around 1975. As I recall: Basically this is a compromise between steepest descent (very slow convergence, but converges from anywhere) and Newton's method (very fast convergence, but converges only close to the optimum). Newton's method also has the disadvantage of requiring computation of the Hessian matrix (the second derivative with respect to all pairs of variables x_i, x_j), or actually it's inverse. This is a very expensive computation. The Newton direction is often not the same direction as the steepest descent. Levenberg-Marquardt attempts to use Newton (or perhaps a variant of Newton, using a positive definite approximation to the Hessian) wherever it gives good descent results, and steepest descent where it doesn't. There is a parameter which causes the update direction to vary between the two directions, and which also controls step size. The algorithm continuously varies this parameter to maintain descent as speedy as possible while ensuring that the steps are indeed descents. -- Randy Poe Johns Hopkins University E-mail: Randall.Poe@jhuapl.edu Applied Physics Laboratory poe@brutus.mts.jhu.edu ============================================================================== From: Steve Bosman Newsgroups: sci.math Subject: Re: Reference for Levernberg-Marquadt theory Date: 31 Jan 1995 14:57:04 GMT el3bpa@sunc.sheffield.ac.uk (B Amavasai) wrote: > > Hi netters, > > I wonder if you could advise me. I'd like to know more > about the Levernberg-Marquadt non-linear optimisation > theory and would be glad if you could recommend me text > which outlines the technique at all levels. > > Thanking you in advance. > > Regards, > Bala > > ---- > el3bpa@sunc.sheffield.ac.uk > Roughly in order of preference I'd recommend the following references:- @BOOK{fle:87, AUTHOR = "R. Fletcher", TITLE = "Practical Methods of Optimization", PUBLISHER = jwiley, YEAR = 1987, NOTE = "LM: roughly page 100 onwards" } @BOOK{gil_mw:81, AUTHOR = "Philip E. Gill and Walter Murray and Margaret H. Wright", TITLE = "Practical Optimization", PUBLISHER = acpress, YEAR = 1981 } @ARTICLE{mar:63, AUTHOR = "Donald W. Marquardt", TITLE = "An Algorithm for the Least-Squares Estimation of Nonlinear Parameters",JOURNAL = "SIAM Journal of Applied Mathematics", VOLUME = 11, NUMBER = 2, MONTH = jun, YEAR = 1963, PAGES = "431--441" } @ARTICLE{lev:44, AUTHOR = "Kenneth Levenberg", TITLE = "A Method for the Solution of Certain Non-linear Problems in Least-Squares", JOURNAL = "Quarterly of Applied Mathematics", VOLUME = 2, NUMBER = 2, YEAR = 1944, MONTH = jul, PAGES = "164--168" } ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Newsgroups: sci.math.research Subject: Re: levenberg marquardt - pappers,tutorial Date: 4 Nov 1998 09:45:42 GMT In article <363F54C8.7B2A2475@lopca.feq.unicamp.br>, eduardo writes: |> I need detais aboul the levenberg marquardt algoritm |> to solve non linear sets of equations. I will use it in incinerator |> energy and mass balace snip J.J. More' : The Levenberg Marquardt algorithm: implementation and theory pages 105-116 in Lecture Notes Masth. 630 (Numerical Analysis, G. Watson ed.), Springer 1977 J.J. More': Recent developments in algorithms and software for trust region methods. Mathematical Programming : The state of the art (Bachem, Korte, Groetschel,eds.) pages 258-287, Springer, Berlin 1983 J.E.Dennis, R.B.Schnabel: Numerical methods for unconstrained optimization and Nonlinear Equations SIAM Classics in Applied Mathematics 1996, pages 227 ff software is in netlib/minpack (lmder.f, lmdif.f . in f77) netlib/cephes (in C) peter ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Newsgroups: comp.lang.fortran,sci.math.num-analysis Subject: Re: non-linear curve fitting Date: 29 Oct 1998 16:16:33 GMT In article <363778E8.6E5B@cfertech.com>, Paul Skoczylas writes: |> I want to fit some data to the following equation: |> Y=(A1*X**2+A2*X+A3)/(X+A4) |> |> The form of this equation is based on the physics of the problem, and I |> can't change it. (Although a polynomial can fit my data very well, it |> does not permit me to extrapolate.) |> |> I used Matlab's optimization toolbox, which (I believe) uses a Marquardt |> method for non-linear curve fitting, and it worked quite well. However, |> I need to translate it into either Fortran or Visual Basic. (The final |> version will be translated into C, but I need to build the algorithms |> which use this curve-fit in a language I can understand...) the levenberg marquardt alogorithm is in netlib : version f77 in minpack version c in cephes. it is very easy to use. what it does: it is a rouitne to minimize sum_{i=1}^N F(i,x)**2 wih respect to x, whatever F(i,.) might be. you have the choice to use it with supplying derivatives of F or not. I propose to compute the derivatives analytically, that is version lmder1.f in minpack what you have to do (in F77) write a function fcn(m,n,x,fvec,fjac,ldfjac,iflag) which computes the following: fvec(i) is the i-th residual , that is fvec(i)=y(i)-(X(1)*t(i)**2+x(2)*t(i)+x(3))/(t(i)+x(4)) I have renamed x-> t and A1=x(1), A2=x(2),..,a4=x(4). n=4, the number of unknowns x(1),..,x(4) i=1,...m the number of measurements. you best supply the data (t(i),y(i)) through common common/userdata/t(100),y(100) (assuming m<=100) in the main program in the subroutine fcn if iflag=1 only fvec has to be computed and fjac must not be touched. if iflag=2 only fjac has to be computed (and fvec not touched) fjac is a matrix, declared externally (it is a parameter to lmder1.f) as double precision fjac(ldfjac,nmax), with nmax>=4 and ldfjac>=m of course. ldfjac and nmax are constants of course in f77. observe that ldfjac is a parameter in lmder1.f and in fcn! to compute ldfjac in your case do i=1,m fjac(i,j)= -(d/d x(j)) (x(1)*t**2+x(2)*t+x(3)/(t+x(4)) at t=t(i) j=1,..,4 enddo this is all you have to do. hope this helps peter ============================================================================== From: Newsgroups: comp.lang.fortran,sci.math.num-analysis Subject: Re: non-linear curve fitting Date: Thu, 29 Oct 1998 21:30:02 -0500 I have used many times the package MINPACK-1 with very good results. The subroutine LMDER in that package implements the Levenberg-Marquardt algorithm for minimization of the sum of squares of non-linear functions when you know the analytical form of the jacobian of the functions. If you do not have an analytical form for the jacobian, there is another subroutine (LMDIF) that uses a numerical approximation and thus, you do not need to provide it. You just have to adjust the subroutine LMDPAR with the right machine parameters for your computer/compiler. The initial lines of the main subroutines (LMDER or LMDIF) are comment lines with fairly clear instructions for their use. You can find the subroutine LMDER and LMDIF (and all MINPACK-1) in netlib at http://www.netlib.org/minpack/index.html (the general address of netlib is http://www.netlib.org/ ). Just click on "minpack/lmder plus dependencies" (for example). I have also used recently a few times the package TENSOLVE and it gave me very good results in minimizing the sum of squares of non-linear functions. This package does not employ the Levenberg-Marquardt algorithm, though. It uses instead a new method, apparently with better results. It also accepts both analytic and numerical jacobians (...and solves systems of non-linear equations; it has everything but the kitchen sink). The TENSOLVE package is Algorithm 768 published in the journal "ACM Transactions on Mathematical Software" (VOL. 232,NO. 21, June, 1997, P. 174--195), where you can find background explanations and bibliography. The package, however, also contains fairly good instructions for its use as comments at the beginning of the main (driver) routines (i.e., subroutines TSNECI and TSNESI). You can find TENSOLVE in netlib as well (under TOMS, Alg.768) in the address http://www.netlib.org/toms/768. A fortran 90 version of TENSOLVE can be found in http://www.ozemail.com.au/~milleraj/misc/toms768.txt (The Home Page of Alan J. Miller); I have not used the fortran 90 version. Finally, another subroutine that seems to have some following is NL2SOL ( http://www.netlib.org/toms/573 ), but I have never used that one. I hope this helps. Julio Escolano Paul Skoczylas wrote in message <363778E8.6E5B@cfertech.com>... >I want to fit some data to the following equation: > Y=(A1*X**2+A2*X+A3)/(X+A4) > >The form of this equation is based on the physics of the problem, and I >can't change it. (Although a polynomial can fit my data very well, it >does not permit me to extrapolate.) > >I used Matlab's optimization toolbox, which (I believe) uses a Marquardt >method for non-linear curve fitting, and it worked quite well. However, >I need to translate it into either Fortran or Visual Basic. (The final >version will be translated into C, but I need to build the algorithms >which use this curve-fit in a language I can understand...) > >I tried using the implementation from Numerical Recipes in Fortran, but >that appears to be buggy, and the description of the algorithm there is >written in a way that my small brain can't understand. > >I tried using a Newton method for fitting non-linear curves, but the >results were most unsatisfactory. > >I also tried finding code at netlib, but the codes I found didn't have >sufficient documentation for my small brain to figure out how to apply >them to my problem. > >Does anyone know of some good references to how to program a Marquardt >method of non-linear curve fitting? Some pseudo-code would be nice, or a >good matrix-based explanation of how the algorithm works... Even some >Fortran code would be okay if it has a good description of how to use >it. > >I appreciate any help anyone can give me. > >-Paul ============================================================================== From: mark@rmplc.co.uk Subject: Re: Levenberg Marquadt parameter limits Date: Fri, 26 Mar 1999 12:54:17 GMT Newsgroups: sci.math,sci.math.num-analysis In article <7dbmvv$tes$1@nnrp1.dejanews.com>, mws@jet.uk wrote: > Hi, I'm using a L-M Chi-squared minimisation routine to estimate some > parameters in my experiment. Thanks to all the people who replied to my posting about this question. I was trying to avoid re-parameterising the equations as this is a nightmare with derivatives, but it was to be my next step if nothing better came along. Upper and lower limits would be trickier still. FYI, I've now found a great book by Gill & Wharton & alii (Practical Optimisation??) 1981 which suggests that LM fit is NOT for constrained parameters, and I should try another method (un-named in the book). This method in this method defines constraints which define the 'feasible' parameter space. I've found that the E04 NAG routines do this work, so I'm going to give it a go with one of them. I was sent a link to a neat NIST USA site: http://math.nist.gov/gams/ which is very good at helping one decide which optimisation routine to use. This pointed me to the same routine I had chosen (yesterday) the hard way. Mark. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own