The method of solving least-squares problems

Linear least squares problems

• Newton's Method
  

Non-Linear least squares problems

• Gauss-Newton Method
  
• Quasi-Newton Method
  
• Gauss-Raphson Method
  
• Levenberg-Marguardt Method
  
• Powell's Dog Leg Method
  
• Hybrid Method: L-M and Quasi-Newton
  

Good references:

• 1999, Poul E. Frandsen, http://www2.imm.dtu.dk/documents/ftp/publlec/lec2_99.pdf
  

Descent method

Conjugate Gradient mehod

Newton-based method, included Quasi-Newton

• 1999, Hans B. Nielsen: http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf
  

Descent method

Gauss-Newton method

Levenberg-Marquardt method

Powell's Dog Leg method

Hybrid: LMA+QN

Newton's Method, NM

Also called Newton-Raphson Method.  It uses the first few terms of the Taylor series (Taylor expansion) of a function  in the vicinity of a suspected root.  

• http://mathworld.wolfram.com/NewtonsMethod.html
  
• http://en.wikipedia.org/wiki/Newton's_method
  

Relationship between Newton's method, Halley method, and Householder's method.

• Newton's method is 1st in the class of Householder's method.
  
• Halley's method is 2nd in the class of Householder's method.
  
• http://en.wikipedia.org/wiki/Householder's_method
  
• http://en.wikipedia.org/wiki/Halley's_method
  

• Levenberg-Marquardt Algorithm, LMA
  
• http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
  
• http://mathworld.wolfram.com/Levenberg-MarquardtMethod.html
  
• http://homepages.inf.ed.ac.uk/cgi/rbf/CVONLINE/entries.pl?TAG49
  
• Nov. 1996, Sam Roweis: http://www.cs.toronto.edu/~roweis/notes/lm.pdf
  
• Good Introduction to talk about the LM from Newton's method, modefied by Levenberg, then modefied by Marquardt to become LM algorithm.
  

1999, Hans B. Nielsen: http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf

Apr. 2004, Hans B. Nielsen: http://www.imm.dtu.dk/pubdb/views/edoc_download.php/3215/pdf/imm3215.pdf

• Above two articles are refered by LEVMAR.
  

June 2004, Ananth R.: http://www.cc.gatech.edu/~ananth/docs/lmtut.pdf

• A good article also to talk about the LM from Newton's, Levenberg, and Marquardt to become LMA.
  

Feb. 2005, Manolis L.: http://www.ics.forth.gr/~lourakis/levmar/levmar.pdf

• The article talking about source code LEVMAR. A pseudocode provided.
  

Nov. 2006, Pradit M.: http://cobweb.ecn.purdue.edu/~kak/courses-i-teach/ECE661.08/homework/HW5_LM_handout.pdf

• Simple example and Matlab code provided.
  

http://www.cse.ucsd.edu/classes/fa04/cse252c/vrabaud1.pdf

• Matlab code, thanks for Pradit Mittrapiyanuruk.
  

Gauss-Newton Method, GNM

• http://en.wikipedia.org/wiki/Gauss-Newton_algorithm
  
• http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationGaussNewtonMethods.html
  
• 1999, Hans B. Nielsen: http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf
  

Gauss-Raphson Method, GRM

Continue..

Quasi-Netwon Method, QNM

• http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
  
• 1999, Poul E. Frandsen, http://www2.imm.dtu.dk/documents/ftp/publlec/lec2_99.pdf
  

Powell's Dog Leg Method, PDLM

• 1999, Hans B. Nielsen: http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf
  

Hybrid Method: L-M and Quasi-Newton, H:LM+QN

• 1999, Hans B. Nielsen: http://www2.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf
  

LMA for linear convergence

QN for superlinear convergence

Papers:

• Yao Jianchao, Chia Tien Chern, COMPARISON OF NEWTON-GAUSS WITH LEVENBERG-MARQUARDT ALGORITHM FOR SPACE RESECTION, Proc. ACRS 2001 - 22nd Asian Conference on Remote Sensing, 5-9 November 2001, Singapore. Vol. 1, pp. 256-261.
  
• C. Kanzow, N. Yamashita and M. Fukushima, Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math.172 (2004), pp. 375–397.
  
• Kanzow, C., Yamashita, N., and Fukushima, M. 2004. Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 172, 2 (Dec. 2004), 375-397. DOI= http://dx.doi.org/10.1016/j.cam.2004.02.013
  
• Lourakis, M. I. and Argyros, A. A. 2005. Is Levenberg-Marquardt the Most Efficient Optimization Algorithm for Implementing Bundle Adjustment?. In Proceedings of the Tenth IEEE international Conference on Computer Vision - Volume 2 (October 17 - 20, 2005). ICCV. IEEE Computer Society, Washington, DC, 1526-1531. DOI= http://dx.doi.org/10.1109/ICCV.2005.128
  

Source codes:

levmar: Levenberg-Marquardt nonlinear least squares algorithms in C/C++

lmfit — a C/C++ routine for Levenberg-Marquardt minimization with wrapper for least-squares curve fitting

lmfit is easy to install it because it is without the dependency problem.

Levenberg-Marquardt for Visual C++ 2005

Levenberg-Marquardt algorithm for multivariate optimization in C#/C++/Delphi/VB6/Zonnon

Continue....