Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-19T09:31:26.372Z Has data issue: false hasContentIssue false
  • English
  • Français

An inexact Levenberg-Marquardt method for large sparse nonlinear least squres

Published online by Cambridge University Press:  17 February 2009

S. J. Wright  and
J. N. Holt
J. N. Holt
Affiliation:
Department of Mathematics, University of Queensland, St. Lucia, 4067, Queensland.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A method for solving problems of the form is presented. The approach of Levenberg and Marquardt is used, except that the linear least squares subproblem arising at each iteration is not solved exactly, but only to within a certain tolerance. The method is most suited to problems in which the Jacobian matrix is sparse. Use is made of the iterative algorithm LSQR of Paige and Saunders for sparse linear least squares.

A global convergence result can be proven, and under certain conditions it can be shown that the method converges quadratically when the sum of squares at the optimal point is zero.

Numerical test results for problems of varying residual size are given.

Type
Research Article
Information
The ANZIAM Journal , Volume 26 , Issue 4 , April 1985 , pp. 387 - 403
Copyright
Copyright © Australian Mathematical Society 1985

References

[1]Altman, M., “Iterative methods of contractor directions”, Nonlinear Anal. 4 (1980), 761–772.CrossRefGoogle Scholar
[2]Bjorck, A. and Duff, I. S., “A direct method for the solution of sparse linear least squares problems”, Linear Algebra Appl. 34 (1980), 43–67.CrossRefGoogle Scholar
[3]Dembo, R., Eisenstat, S. and Steihaug, T., “Inexact Newton methods”, SIAM J. Numer. Anal. 19 (1982), 400–408.CrossRefGoogle Scholar
[4]Dembo, R. and Steihaug, T., “Truncated Newton algorithms for large-scale unconstrained optimization”, Math Programming 26 (1983), 190–212.CrossRefGoogle Scholar
[5]Dennis, J., Gay, D. and Welsch, R., “An adaptive nonlinear least-squares algorithm”, ACM Trans. Math. Software 7 (1981), 348–368.CrossRefGoogle Scholar
[6]Gill, P., Murray, W. and Nash, S., (to appear).Google Scholar
[7]Golub, G. and Kahan, W., “Calculating the singular values and pseudoinverse of a matrix”, SIAM J. Numer. Anal. 2 (1965), 205–224.Google Scholar
[8]Golub, G. and Plemmons, R., “Large-scale geodetic least squares adjustment by dissection and orthogonal decomposition”, Linear Algebra Appl. 34 (1980), 3–27.CrossRefGoogle Scholar
[9]Hiebert, K., “An evaluation of mathematical software that solves nonlinear least squares problems”, ACM Trans. Math Software 7 (1981), 1–16.CrossRefGoogle Scholar
[10]Holt, J. N. and Fletcher, R., “An algorithm for constrained nonlinear least squares”, J. Inst. Math. Appl. 23 (1979), 449–463.CrossRefGoogle Scholar
[11]Lee, W. and Stewart, S., Principles and applications of microearthquake networks (Academic Press, New York, 1981).Google Scholar
[12]Levenberg, K., “A method for the solution of certain nonlinear problems in least squares”, Quart. Appl. Math. 2 (1944), 164–168.CrossRefGoogle Scholar
[13]Marquardt, D., “An algorithm for least squares estimation of nonlinear parameters”, SIAM J. Appl. Math. 11 (1963), 431–441.CrossRefGoogle Scholar
[14]Moré, J., “The Levenberg-Marquardt algorithm: Implementation and theory”, in Numerical analysis (ed. Watson, G. A.), Lecture Notes in Math. 630 (Springer-Verlag, New York, 1977), 105–116.Google Scholar
[15]Osborne, M., “Nonlinear least squares—the Levenberg-Marquardt algorithm revisited”, J. Austral. Math. Soc. Ser. B 19 (1976), 343–357.CrossRefGoogle Scholar
[16]Paige, C. and Saunders, M., “LSQR: An algorithm for sparse linear equations and sparse least squares”, ACM Trans. Math. Software 8 (1982), 43–71.CrossRefGoogle Scholar
[17]Steihaug, T., “The conjugate gradient method and trust regions in large scale optimization”. SIAM J. Numer. Anal. 20 (1983), 626–637.CrossRefGoogle Scholar
[18]Wright, S. and Holt, J., “Algorithms for nonlinear least squares with linear inequality constraints”, SIAM J. Sci. Statist. Comput. (to appear).Google Scholar