Advanced Search
Article Contents
Article Contents

A brief survey of methods for solving nonlinear least-squares problems

  • * Corresponding author: Hassan Mohammad.

    * Corresponding author: Hassan Mohammad. 
Abstract Full Text(HTML) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 93E24, 49M37; Secondary: 65K05, 90C53, 49J52.


    \begin{equation} \\ \end{equation}
  • 加载中
  •   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.
  • 加载中

Article Metrics

HTML views(3888) PDF downloads(1841) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint