In this paper, we present a brief survey of methods for solving nonlinear least-squares problems. We pay specific attention to methods that take into account the special structure of the problems. Most of the methods discussed belong to the quasi-Newton family (i.e. the structured quasi-Newton methods (SQN)). Our survey comprises some of the traditional and modern developed methods for nonlinear least-squares problems. At the end, we suggest a few topics for further research.
Citation: |
M. Al-Baali, Quasi-newton algorithms for large-scale nonlinear least-squares, in High Performance Algorithms and Software for Nonlinear Optimization, Springer, (2003), 1-21.
doi: 10.1007/978-1-4613-0241-4_1.![]() ![]() ![]() |
|
M. Al-Baali
and R. Fletcher
, Variational methods for non-linear least-squares, J. Oper. Res. Soc., 36 (1985)
, 405-421.
![]() |
|
M. C. Bartholomew-Biggs
, The estimation of the Hessian matrix in nonlinear least squares problems with non-zero residuals, Math. Program., 12 (1977)
, 67-80.
doi: 10.1007/BF01593770.![]() ![]() ![]() |
|
S. Bellavia
, C. Cartis
, N. I. M. Gould
, B. Morini
and P. L. Toint
, Convergence of a regularized Euclidean residual algorithm for nonlinear least-squares, SIAM J. Numer. Anal., 48 (2010)
, 1-29.
doi: 10.1137/080732432.![]() ![]() ![]() |
|
J. T. Betts
, Solving the nonlinear least square problem: Application of a general method, J. Optim. Theory Appl., 18 (1976)
, 469-483.
doi: 10.1007/BF00932656.![]() ![]() ![]() |
|
E. G. Birgin
, J. L. Gardenghi
, J. M. Martínez
, S. A. Santos
and P. L. Toint
, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Program., 163 (2017)
, 359-368.
doi: 10.1007/s10107-016-1065-8.![]() ![]() ![]() |
|
K. M. Brown
and J. E. Dennis
, Derivative-free analogues of the Levenberg-Marquardt and Gauss algorithms for nonlinear least squares approximation, Numer. Math., 18 (1971)
, 289-297.
doi: 10.1007/BF01404679.![]() ![]() ![]() |
|
K. M. Brown and J. E. Dennis, A new algorithm for nonlinear least-squares curve fitting, in Mathematical Software (ed. J. R. Rice), Academic Press, New York, (1971), 391-396.
![]() |
|
C. G. Broyden
, A class of methods for solving nonlinear simultaneous equations, Math. Comput., 19 (1965)
, 577-593.
doi: 10.2307/2003941.![]() ![]() ![]() |
|
C. Cartis
, N. I. M. Gould
and P. L. Toint
, On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization, SIAM J. Optim., 23 (2013)
, 1553-1574.
doi: 10.1137/120869687.![]() ![]() ![]() |
|
C. Cartis
, N. I. M. Gould
and P. L. Toint
, On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods, SIAM J. Numer. Anal., 53 (2015)
, 836-851.
doi: 10.1137/130915546.![]() ![]() ![]() |
|
A. Cornelio
, Regularized nonlinear least squares methods for hit position reconstruction in small gamma cameras, Appl. Math. Comput., 217 (2011)
, 5589-5595.
doi: 10.1016/j.amc.2010.12.035.![]() ![]() |
|
J. E. Dennis, Some computational techniques for the nonlinear least squares problem, in Numerical Solution of Systems of Nonlinear Algebraic Equations (eds. G. D. Byrne and C. A. Hall), Academic Press, New York, (1973), 157-183.
![]() ![]() |
|
J. E. Dennis and R. B. Schnabel Jr, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, 1983.
![]() ![]() |
|
J. E. Dennis Jr
, D. M. Gay
and R. E. Walsh
, An adaptive nonlinear least-squares algorithm, ACM Trans. Math. Software (TOMS), 7 (1981)
, 348-368.
doi: 10.1145/355958.355965.![]() ![]() |
|
R. Fletcher
and C. Xu
, Hybrid methods for nonlinear least squares, IMA J. Numer. Anal., 7 (1987)
, 371-389.
doi: 10.1093/imanum/7.3.371.![]() ![]() ![]() |
|
G. Golub
and V. Pereyra
, Separable nonlinear least squares: the variable projection method and its applications, Inverse Problems, 19 (2003)
, R1-R26.
doi: 10.1088/0266-5611/19/2/201.![]() ![]() ![]() |
|
D. S. Gonçalves
and S. A. Santos
, A globally convergent method for nonlinear least-squares problems based on the Gauss-Newton model with spectral correction, Bull. Comput. Appl. Math., 4 (2016)
, 7-26.
![]() ![]() |
|
D. S. Gonçalves
and S. A. Santos
, Local analysis of a spectral correction for the Gauss-Newton model applied to quadratic residual problems, Numer. Algorithms, 73 (2016)
, 407-431.
doi: 10.1007/s11075-016-0101-3.![]() ![]() ![]() |
|
N. Gould
, S. Leyffer
and P. L. Toint
, A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim., 15 (2004)
, 17-38.
doi: 10.1137/S1052623403422637.![]() ![]() ![]() |
|
G. N. Grapiglia
, J. Yuan
and Y. X. Yuan
, On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization, Math. Program., 152 (2015)
, 491-520.
doi: 10.1007/s10107-014-0794-9.![]() ![]() ![]() |
|
S. Gratton
, A. S. Lawless
and N. K. Nichols
, Approximate Gauss-Newton methods for nonlinear least squares problems, SIAM J. Optim., 18 (2007)
, 106-132.
doi: 10.1137/050624935.![]() ![]() ![]() |
|
A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, Vol. 105, 2008.
doi: 10.1137/1.9780898717761.![]() ![]() ![]() |
|
H. O. Hartley
, The modified Gauss-Newton method for the fitting of non-linear regression functions by least squares, Technometrics, 3 (1961)
, 269-280.
doi: 10.2307/1266117.![]() ![]() ![]() |
|
S. Henn
, A Levenberg-Marquardt scheme for nonlinear image registration, BIT, 43 (2003)
, 743-759.
doi: 10.1023/B:BITN.0000009940.58397.98.![]() ![]() ![]() |
|
J. Huschens
, On the use of product structure in secant methods for nonlinear least squares problems, SIAM J. Optim., 4 (1994)
, 108-129.
doi: 10.1137/0804005.![]() ![]() ![]() |
|
E. W. Karas
, S. A. Santos
and B. F. Svaiter
, Algebraic rules for computing the regularization parameter of the Levenberg-Marquardt method, Comput. Optim. Appl., 65 (2016)
, 723-751.
doi: 10.1007/s10589-016-9845-x.![]() ![]() ![]() |
|
S. Kim
, K. Koh
, M. Lustig
, S. Boyd
and D. Gorinevsky
, An interior-point method for large-scale $\ell _1 $-regularized least squares, IEEE. J. Sel. Top. Signa., 1 (2007)
, 606-617.
![]() ![]() |
|
D. A. Knoll
and D. E. Keyes
, Jacobian-free Newton-Krylov methods: a survey of approaches and applications, J. Comput. Phys., 193 (2004)
, 357-397.
doi: 10.1016/j.jcp.2003.08.010.![]() ![]() ![]() |
|
M. Kobayashi
, Y. Narushima
and H. Yabe
, Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems, J. Comput. Appl. Math., 234 (2010)
, 375-397.
doi: 10.1016/j.cam.2009.12.031.![]() ![]() ![]() |
|
K. Levenberg
, A method for the solution of certain non-linear problems in least squares, Quarter. Appl. Math., 2 (1944)
, 164-168.
doi: 10.1090/qam/10666.![]() ![]() ![]() |
|
D.-H. Li
and M. Fukushima
, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129 (2001)
, 15-35.
doi: 10.1016/S0377-0427(00)00540-9.![]() ![]() ![]() |
|
J. Li
, F. Ding
and G. Yang
, Maximum likelihood least squares identification method for input nonlinear finite impulse response moving average systems, Math. Comput. Model., 55 (2012)
, 442-450.
doi: 10.1016/j.mcm.2011.08.023.![]() ![]() ![]() |
|
D. C. López
, T. Barz
, S. Korkel
and G. Wozny
, Nonlinear ill-posed problem analysis in model-based parameter estimation and experimental design, Comput. Chem. Eng., 77 (2015)
, 24-42.
doi: 10.1016/j.compchemeng.2015.03.002.![]() ![]() |
|
L. Lukšan
, Hybrid methods for large sparse nonlinear least squares, J. Optim. Theory Appl., 89 (1996)
, 575-595.
doi: 10.1007/BF02275350.![]() ![]() ![]() |
|
D. W. Marquardt
, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Ind. Appl. Math., 11 (1963)
, 431-441.
![]() ![]() |
|
J. J. McKeown
, Specialised versus general-purpose algorithms for minimising functions that are sums of squared terms, Math. Program., 9 (1975)
, 57-68.
doi: 10.1007/BF01681330.![]() ![]() ![]() |
|
F. Modarres
, M. A. Hassan
and W. J. Leong
, Structured symmetric rank-one method for unconstrained optimization, Int. J. Comput. Math., 88 (2011)
, 2608-2617.
doi: 10.1080/00207160.2011.553220.![]() ![]() ![]() |
|
H. Mohammad and S. A. Santos, A structured diagonal Hessian approximation method with evaluation complexity analysis for nonlinear least squares, Computational and Applied Mathematics, online.
doi: 10.1007/s40314-018-0696-1.![]() ![]() |
|
D. D. Morrison, Methods for nonlinear least squares problems and convergence proofs, in Proceedings of the Seminar on Tracking Programs and Orbit Determination (eds. J. Lorell and F. Yagi), Jet Propulsion Laboratory, Pasadena, (1960), 1-9.
![]() |
|
L. Nazareth, An Adaptive Method for Minimizing a Sum of Squares of Nonlinear Functions, NASA Report WP-83-99, 1983.
![]() |
|
L. Nazareth
, Some recent approaches to solving large residual nonlinear least squares problems, SIAM Review, 22 (1980)
, 1-11.
doi: 10.1137/1022001.![]() ![]() ![]() |
|
Y. Nesterov
, Modified Gauss-Newton scheme with worst case guarantees for global performance, Optim. Methods Softw., 22 (2007)
, 469-483.
doi: 10.1080/08927020600643812.![]() ![]() ![]() |
|
J. Nocedal and S. J. Wright, Numerical Optimization, Springer Science, 2006.
doi: 10.1007/978-0-387-40065-5.![]() ![]() ![]() |
|
S. S. Oren
, On the selection of parameters in self scaling variable metric algorithms, Math. Program., 7 (1974)
, 351-367.
doi: 10.1007/BF01585530.![]() ![]() ![]() |
|
S. S. Oren
and D. G. Luenberger
, Self-scaling variable metric (SSVM) algorithms: Part Ⅰ: Criteria and sufficient conditions for scaling a class of algorithms, Management Science, 20 (1974)
, 845-862.
doi: 10.1287/mnsc.20.5.845.![]() ![]() ![]() |
|
G. Peckham
, A new method for minimising a sum of squares without calculating gradients, The Comput. J., 13 (1970)
, 418-420.
doi: 10.1093/comjnl/13.4.418.![]() ![]() ![]() |
|
M. Porcelli
, On the convergence of an inexact Gauss--Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Lett., 7 (2013)
, 447-465.
doi: 10.1007/s11590-011-0430-z.![]() ![]() ![]() |
|
M. J. D. Powell
, A method for minimizing a sum of squares of non-linear functions without calculating derivatives, The Comput. J., 7 (1965)
, 303-307.
doi: 10.1093/comjnl/7.4.303.![]() ![]() ![]() |
|
M. L. Ralston
and R. I. Jennrich
, DUD, A derivative-free algorithm for nonlinear least squares, Technometrics, 20 (1978)
, 7-14.
doi: 10.1080/00401706.1978.10489610.![]() ![]() |
|
H. Ren
, I. K. Argyros
and S. Hilout
, A derivative-free iterative method for solving least squares problems, Numer. Algorithms, 58 (2011)
, 555-571.
doi: 10.1007/s11075-011-9470-9.![]() ![]() ![]() |
|
S. M. Shakhno
and O. P. Gnatyshyn
, On an iterative algorithm of order 1.839 ... for solving the nonlinear least squares problems, Appl. Math. Comput., 161 (2005)
, 253-264.
doi: 10.1016/j.amc.2003.12.025.![]() ![]() ![]() |
|
S. Sheng and Z. Zou, A New Secant Method for Nonlinear Least Squares Problems, Report NANOG 1988-03, Nanjing University, China, 1988.
![]() |
|
E. Spedicato
and M. T. Vespucci
, Numerical experiments with variations of the Gauss-Newton algorithm for nonlinear least squares, J. Optim. Theory Appl., 57 (1988)
, 323-339.
doi: 10.1007/BF00938543.![]() ![]() ![]() |
|
W. Sun and Y. X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer Science, 2006.
doi: 10.1007/b106451.![]() ![]() ![]() |
|
L. Tang, A regularization homotopy iterative method for ill-posed nonlinear least squares problem and its application, in Advances in Civil Engineering, ICCET 2011, vol. 90 of Applied Mechanics and Materials, Trans Tech Publications, 2011, 3268-3273.
doi: 10.4028/www.scientific.net/AMM.90-93.3268.![]() ![]() |
|
P. L. Toint
, On large scale nonlinear least squares calculations, SIAM J. Sci. Stat. Comput., 8 (1987)
, 416-435.
doi: 10.1137/0908042.![]() ![]() ![]() |
|
F. Wang
, D. H. Li
and L. Qi
, Global convergence of Gauss-Newton-MBFGS method for solving the nonlinear least squares problem, Advan. Model. Optim., 12 (2010)
, 1-19.
![]() ![]() |
|
C. X. Xu
, Hybrid method for nonlinear least-square problems without calculating derivatives, J. Optim. Theory Appl., 65 (1990)
, 555-574.
doi: 10.1007/BF00939566.![]() ![]() ![]() |
|
W. Xu
, T. F. Coleman
and G. Liu
, A secant method for nonlinear least-squares minimization, Comput. Optim. Appl., 51 (2012)
, 159-173.
doi: 10.1007/s10589-010-9336-4.![]() ![]() ![]() |
|
W. Xu
, N. Zheng
and K. Hayami
, Jacobian-free implicit inner-iteration preconditioner for nonlinear least squares problems, J. Sci. Comput., 68 (2016)
, 1055-1081.
doi: 10.1007/s10915-016-0167-z.![]() ![]() ![]() |
|
H. Yabe
, Variations of structured Broyden families for nonlinear least squares problems, Optim. Methods Softw., 2 (1993)
, 107-144.
![]() ![]() |
|
H. Yabe
and H. Ogasawara
, Quadratic and superlinear convergence of the Huschen's method for nonlinear least squares problems, Comput. Optim. Appl., 10 (1998)
, 79-103.
doi: 10.1023/A:1018391917880.![]() ![]() ![]() |
|
H. Yabe
and T. Takahashi
, Structured quasi-newton methods for nonlinear least squares problems, TRU Math., 24 (1988)
, 195-209.
![]() ![]() |
|
H. Yabe
and T. Takahashi
, Factorized quasi-newton methods for nonlinear least squares problems, Math. Program., 51 (1991)
, 75-100.
doi: 10.1007/BF01586927.![]() ![]() ![]() |
|
H. Yabe
and T. Takahashi
, Numerical Comparison among structured quasi-Newton methods for nonlinear least squares problems, J. Oper. Res. Soc. Japan, 34 (1991)
, 287-305.
doi: 10.15807/jorsj.34.287.![]() ![]() |
|
H. Yabe
and N. Yamaki
, Convergence of a factorized Broyden-like family for nonlinear least squares problems, SIAM J. Optim., 5 (1995)
, 770-791.
doi: 10.1137/0805037.![]() ![]() ![]() |
|
Y. X. Yuan
, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numer. Algebr., Contr. Optim., 1 (2011)
, 15-34.
doi: 10.3934/naco.2011.1.15.![]() ![]() ![]() |
|
H. Zhang
and A. R. Conn
, On the local convergence of a derivative-free algorithm for least-squares minimization, Comput. Optim. Appl., 51 (2012)
, 481-507.
doi: 10.1007/s10589-010-9367-x.![]() ![]() ![]() |
|
H. Zhang
, A. R. Conn
and K. Scheinberg
, A derivative-free algorithm for least-squares minimization, SIAM J. Optim., 20 (2010)
, 3555-3576.
doi: 10.1137/09075531X.![]() ![]() ![]() |
|
H. Zhang
and W. W. Hager
, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004)
, 1043-1056.
doi: 10.1137/S1052623403428208.![]() ![]() ![]() |
|
J. Z. Zhang
, L. H. Chen
and N. Y. Deng
, A family of scaled factorized Broyden-like methods for nonlinear least squares problems, SIAM J. Optim., 10 (2000)
, 1163-1179.
doi: 10.1137/S1052623498345300.![]() ![]() ![]() |
|
J. Zhang
, Y. Xue
and K. Zhang
, A structured secant method based on a new quasi-newton equation for nonlinear least squares problems, BIT, 43 (2003)
, 217-229.
doi: 10.1023/A:1023665409152.![]() ![]() ![]() |
|
R. Zhao
and J. Fan
, Global complexity bound of the Levenberg-Marquardt method, Optim. Methods Softw., 31 (2016)
, 805-814.
doi: 10.1080/10556788.2016.1179737.![]() ![]() ![]() |
|
W. Zhou
and X. Chen
, Global convergence of new hybrid Gauss-Newton structured BFGS method for nonlinear least squares problems, SIAM J. Optim., 20 (2010)
, 2422-2441.
doi: 10.1137/090748470.![]() ![]() ![]() |