2011, 1(1): 15-34. doi: 10.3934/naco.2011.1.15

Recent advances in numerical methods for nonlinear equations and nonlinear least squares

1. 

State Key Laboratory of Scientific/Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Zhong Guan Cun Donglu 55, Beijing, 100190, China

Received  June 2010 Revised  September 2010 Published  February 2011

Nonlinear equations and nonlinear least squares problems have many applications in physics, chemistry, engineering, biology, economics, finance and many other fields. In this paper, we will review some recent results on numerical methods for these two special problems, particularly on Levenberg-Marquardt type methods, quasi-Newton type methods, and trust region algorithms. Discussions on variable projection methods and subspace methods are also given. Some theoretical results about local convergence results of the Levenberg-Marquardt type methods without non-singularity assumption are presented. A few model algorithms based on line searches and trust regions are also given.
Citation: Ya-Xiang Yuan. Recent advances in numerical methods for nonlinear equations and nonlinear least squares. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 15-34. doi: 10.3934/naco.2011.1.15
References:
[1]

IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[2]

SIAM J. Numer. Anal., 48 (2010), 1-29. doi: 10.1137/080732432.  Google Scholar

[3]

Future Generation Computer Systems, 18 (2001), 41-53. doi: 10.1016/S0167-739X(00)00074-1.  Google Scholar

[4]

Numerical Algorithms, 32 (2003), 249-260. doi: 10.1023/A:1024013824524.  Google Scholar

[5]

Computational Optimization and Applications, 7 (1997), 27-40. doi: 10.1023/A:1008628114432.  Google Scholar

[6]

Ph.D. thesis, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. Google Scholar

[7]

Science in China, Ser. A., 53 (2010), 1-10. doi: 10.1007/s11425-010-4056-x.  Google Scholar

[8]

MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2000. Google Scholar

[9]

SIAM Review, 19 (1977), 46-89. doi: 10.1137/1019005.  Google Scholar

[10]

SIAM, Philadelphia, 1993. Google Scholar

[11]

Computing, 74 (2005), 23-39. doi: 10.1007/s00607-004-0083-1.  Google Scholar

[12]

Report, AMSS, CAS, Beijing, 2010. Google Scholar

[13]

Math. Program., 17 (1982), 67-76.  Google Scholar

[14]

Second Edition, John Wiley and Sons, 1987.  Google Scholar

[15]

IMA J. Numerical Analysis, 7 (1987), 371-389. doi: 10.1093/imanum/7.3.371.  Google Scholar

[16]

SIAM J. Numer. Anal, 10 (1973), 413-432. doi: 10.1137/0710036.  Google Scholar

[17]

Inverse Problems, 19 (2003), 1-26. doi: 10.1088/0266-5611/19/2/201.  Google Scholar

[18]

Johns Hopkins University Press, Baltimore and London, 1996. Google Scholar

[19]

Acta Numerica, 299-361, 2005. doi: 10.1017/S0962492904000248.  Google Scholar

[20]

ACM Transactions on Mathematical Software (TOMS), 33 (2007), 3-25. doi: 10.1145/1206040.1206043.  Google Scholar

[21]

Frontiers in Applied Mathematics, Vol 19, SIAM, Philadelphia, PA, 2000.  Google Scholar

[22]

Optimizaiton Methods and Software, 17 (2002), 869-889. doi: 10.1080/1055678021000060829.  Google Scholar

[23]

BIT, 15 (1975), 49-57. doi: 10.1007/BF01932995.  Google Scholar

[24]

SIAM, Philadelphia, 1995.  Google Scholar

[25]

Fundamentals of Algorithms Series, SIAM, Philadelphia, 2003.  Google Scholar

[26]

J. Comp. Appl. Math., 173 (2005), 321-343.  Google Scholar

[27]

Optimization Methods and Software, 18 (2003), 583-599. doi: 10.1080/10556780310001610493.  Google Scholar

[28]

Math. Comp., 75 (2006), 1429-1448. doi: 10.1090/S0025-5718-06-01840-0.  Google Scholar

[29]

SIAM J. Numer. Anal., 37 (1999), 152-172. doi: 10.1137/S0036142998335704.  Google Scholar

[30]

Optimizaiton Methods and Software, 13 (2000), 181-201. doi: 10.1080/10556780008805782.  Google Scholar

[31]

J. Comput. Math., 26 (2008), 390-403.  Google Scholar

[32]

Computing, 33 (1984), 353-362.  Google Scholar

[33]

Neural Networks, 16 (2003), 745-753. doi: 10.1016/S0893-6080(03)00085-6.  Google Scholar

[34]

in "Lecture Notes in Mathematics 630: Numerical Analysis"(eds. G.A. Watson), Springer-Verlag, Berlin, 1978, pp. 105-116.  Google Scholar

[35]

in "Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, 1983)"(eds. A. Bachem, M. Grötschel and B. Korte), pp. 258-287.  Google Scholar

[36]

SIAM J. Sci. Statist. Compute., 4 (1983), 553-572. doi: 10.1137/0904038.  Google Scholar

[37]

Optimization Methods and Sofware, 22 (2007), 469-483. doi: 10.1080/08927020600643812.  Google Scholar

[38]

Springer, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[39]

Academic Press, New York and London, 1970.  Google Scholar

[40]

in "Nonlinear Programming"(eds. J.B. Rosen, O.L. Mangasarian and K. Ritter), pp. 31-65, Academic Press, New York, 1970.  Google Scholar

[41]

The Computer J., 7 (1965), 303-307.  Google Scholar

[42]

in "Numerical Methods for Nonlinear Algebraic Equations"(eds. P. Robinowtiz), Gordon and Breach, London, 1970, pp. 87-114.  Google Scholar

[43]

in "Numerical Analysis"(eds. G.A. Watson), Springer, Berlin, 1978, pp. 144-157. doi: 10.1007/BFb0067703.  Google Scholar

[44]

IMA J. Numerical Analysis, 4 (1984), 241-251. doi: 10.1093/imanum/4.2.241.  Google Scholar

[45]

SIAM Review, 22 (1980), 318-337. doi: 10.1137/1022057.  Google Scholar

[46]

SIAM, New York, 2003. doi: 10.1137/1.9780898718003.  Google Scholar

[47]

Math. Program., 121 (2010), 221-247. doi: 10.1007/s10107-008-0232-y.  Google Scholar

[48]

in "Trends in Mathematical Optimization"(eds. K.H. Hoffmann, J.-B. Hiriart-Urruty, C. Lemarechal, J. Zowe), International Series of Numerical Mathematics, Vol. 84, Birkhäuser, Boston, 1988, pp. 295-309.  Google Scholar

[49]

Applied Optimization Vol. 77, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[50]

Math. Comp., 24 (1970), 27-30. doi: 10.1090/S0025-5718-1970-0258276-9.  Google Scholar

[51]

SIAM J. Numerical Analysis, 20 (1983), 626-637. doi: 10.1137/0720042.  Google Scholar

[52]

Z. Angew. Math. Mech., 75 (1995), 69-77. doi: 10.1002/zamm.19950750118.  Google Scholar

[53]

Springer Series on Optimization and Its Application, Vol. 1, Springer, 2006. Google Scholar

[54]

Mathematics of Computation, 31 (1977), 954-961. doi: 10.1090/S0025-5718-1977-0455338-4.  Google Scholar

[55]

in "Sparse Matrices and Their Uses"( eds. I. Duff), Academic Press, 1981, pp. 57-88. Google Scholar

[56]

SIAM J. Sci. Stat. Comput., 8 (1987), 416-435. doi: 10.1137/0908042.  Google Scholar

[57]

Numerische Mathematik, 104 (2006), 241-269. doi: 10.1007/s00211-006-0021-6.  Google Scholar

[58]

Computing, (Supplement) 15 (2001), 237-249. Google Scholar

[59]

Information, 1 (1998), 7-20.  Google Scholar

[60]

Math. Program., 87 (2000), 561-573. doi: 10.1007/s101070050012.  Google Scholar

[61]

in "Some Topics in Industrial and Applied Mathematics" (eds. R. Jeltsch, D.Q. Li and I. H. Sloan), (Series in Contemporary Applied Mathematics CAM 8) Higher Education Press. Beijing, 2007, pp. 206-218.  Google Scholar

[62]

Optimization and Engineering, 10 (2009), 207-218. doi: 10.1007/s11081-008-9064-0.  Google Scholar

[63]

H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for the least-squares minimization,, , ().   Google Scholar

[64]

H. C. Zhang, A. R. Conn and K. Scheinberg, On the local convergence of a derivative-free algorithm for least-squares minimization,, , ().   Google Scholar

show all references

References:
[1]

IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[2]

SIAM J. Numer. Anal., 48 (2010), 1-29. doi: 10.1137/080732432.  Google Scholar

[3]

Future Generation Computer Systems, 18 (2001), 41-53. doi: 10.1016/S0167-739X(00)00074-1.  Google Scholar

[4]

Numerical Algorithms, 32 (2003), 249-260. doi: 10.1023/A:1024013824524.  Google Scholar

[5]

Computational Optimization and Applications, 7 (1997), 27-40. doi: 10.1023/A:1008628114432.  Google Scholar

[6]

Ph.D. thesis, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. Google Scholar

[7]

Science in China, Ser. A., 53 (2010), 1-10. doi: 10.1007/s11425-010-4056-x.  Google Scholar

[8]

MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2000. Google Scholar

[9]

SIAM Review, 19 (1977), 46-89. doi: 10.1137/1019005.  Google Scholar

[10]

SIAM, Philadelphia, 1993. Google Scholar

[11]

Computing, 74 (2005), 23-39. doi: 10.1007/s00607-004-0083-1.  Google Scholar

[12]

Report, AMSS, CAS, Beijing, 2010. Google Scholar

[13]

Math. Program., 17 (1982), 67-76.  Google Scholar

[14]

Second Edition, John Wiley and Sons, 1987.  Google Scholar

[15]

IMA J. Numerical Analysis, 7 (1987), 371-389. doi: 10.1093/imanum/7.3.371.  Google Scholar

[16]

SIAM J. Numer. Anal, 10 (1973), 413-432. doi: 10.1137/0710036.  Google Scholar

[17]

Inverse Problems, 19 (2003), 1-26. doi: 10.1088/0266-5611/19/2/201.  Google Scholar

[18]

Johns Hopkins University Press, Baltimore and London, 1996. Google Scholar

[19]

Acta Numerica, 299-361, 2005. doi: 10.1017/S0962492904000248.  Google Scholar

[20]

ACM Transactions on Mathematical Software (TOMS), 33 (2007), 3-25. doi: 10.1145/1206040.1206043.  Google Scholar

[21]

Frontiers in Applied Mathematics, Vol 19, SIAM, Philadelphia, PA, 2000.  Google Scholar

[22]

Optimizaiton Methods and Software, 17 (2002), 869-889. doi: 10.1080/1055678021000060829.  Google Scholar

[23]

BIT, 15 (1975), 49-57. doi: 10.1007/BF01932995.  Google Scholar

[24]

SIAM, Philadelphia, 1995.  Google Scholar

[25]

Fundamentals of Algorithms Series, SIAM, Philadelphia, 2003.  Google Scholar

[26]

J. Comp. Appl. Math., 173 (2005), 321-343.  Google Scholar

[27]

Optimization Methods and Software, 18 (2003), 583-599. doi: 10.1080/10556780310001610493.  Google Scholar

[28]

Math. Comp., 75 (2006), 1429-1448. doi: 10.1090/S0025-5718-06-01840-0.  Google Scholar

[29]

SIAM J. Numer. Anal., 37 (1999), 152-172. doi: 10.1137/S0036142998335704.  Google Scholar

[30]

Optimizaiton Methods and Software, 13 (2000), 181-201. doi: 10.1080/10556780008805782.  Google Scholar

[31]

J. Comput. Math., 26 (2008), 390-403.  Google Scholar

[32]

Computing, 33 (1984), 353-362.  Google Scholar

[33]

Neural Networks, 16 (2003), 745-753. doi: 10.1016/S0893-6080(03)00085-6.  Google Scholar

[34]

in "Lecture Notes in Mathematics 630: Numerical Analysis"(eds. G.A. Watson), Springer-Verlag, Berlin, 1978, pp. 105-116.  Google Scholar

[35]

in "Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, 1983)"(eds. A. Bachem, M. Grötschel and B. Korte), pp. 258-287.  Google Scholar

[36]

SIAM J. Sci. Statist. Compute., 4 (1983), 553-572. doi: 10.1137/0904038.  Google Scholar

[37]

Optimization Methods and Sofware, 22 (2007), 469-483. doi: 10.1080/08927020600643812.  Google Scholar

[38]

Springer, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[39]

Academic Press, New York and London, 1970.  Google Scholar

[40]

in "Nonlinear Programming"(eds. J.B. Rosen, O.L. Mangasarian and K. Ritter), pp. 31-65, Academic Press, New York, 1970.  Google Scholar

[41]

The Computer J., 7 (1965), 303-307.  Google Scholar

[42]

in "Numerical Methods for Nonlinear Algebraic Equations"(eds. P. Robinowtiz), Gordon and Breach, London, 1970, pp. 87-114.  Google Scholar

[43]

in "Numerical Analysis"(eds. G.A. Watson), Springer, Berlin, 1978, pp. 144-157. doi: 10.1007/BFb0067703.  Google Scholar

[44]

IMA J. Numerical Analysis, 4 (1984), 241-251. doi: 10.1093/imanum/4.2.241.  Google Scholar

[45]

SIAM Review, 22 (1980), 318-337. doi: 10.1137/1022057.  Google Scholar

[46]

SIAM, New York, 2003. doi: 10.1137/1.9780898718003.  Google Scholar

[47]

Math. Program., 121 (2010), 221-247. doi: 10.1007/s10107-008-0232-y.  Google Scholar

[48]

in "Trends in Mathematical Optimization"(eds. K.H. Hoffmann, J.-B. Hiriart-Urruty, C. Lemarechal, J. Zowe), International Series of Numerical Mathematics, Vol. 84, Birkhäuser, Boston, 1988, pp. 295-309.  Google Scholar

[49]

Applied Optimization Vol. 77, Kluwer Academic Publishers, Dordrecht, 2002.  Google Scholar

[50]

Math. Comp., 24 (1970), 27-30. doi: 10.1090/S0025-5718-1970-0258276-9.  Google Scholar

[51]

SIAM J. Numerical Analysis, 20 (1983), 626-637. doi: 10.1137/0720042.  Google Scholar

[52]

Z. Angew. Math. Mech., 75 (1995), 69-77. doi: 10.1002/zamm.19950750118.  Google Scholar

[53]

Springer Series on Optimization and Its Application, Vol. 1, Springer, 2006. Google Scholar

[54]

Mathematics of Computation, 31 (1977), 954-961. doi: 10.1090/S0025-5718-1977-0455338-4.  Google Scholar

[55]

in "Sparse Matrices and Their Uses"( eds. I. Duff), Academic Press, 1981, pp. 57-88. Google Scholar

[56]

SIAM J. Sci. Stat. Comput., 8 (1987), 416-435. doi: 10.1137/0908042.  Google Scholar

[57]

Numerische Mathematik, 104 (2006), 241-269. doi: 10.1007/s00211-006-0021-6.  Google Scholar

[58]

Computing, (Supplement) 15 (2001), 237-249. Google Scholar

[59]

Information, 1 (1998), 7-20.  Google Scholar

[60]

Math. Program., 87 (2000), 561-573. doi: 10.1007/s101070050012.  Google Scholar

[61]

in "Some Topics in Industrial and Applied Mathematics" (eds. R. Jeltsch, D.Q. Li and I. H. Sloan), (Series in Contemporary Applied Mathematics CAM 8) Higher Education Press. Beijing, 2007, pp. 206-218.  Google Scholar

[62]

Optimization and Engineering, 10 (2009), 207-218. doi: 10.1007/s11081-008-9064-0.  Google Scholar

[63]

H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for the least-squares minimization,, , ().   Google Scholar

[64]

H. C. Zhang, A. R. Conn and K. Scheinberg, On the local convergence of a derivative-free algorithm for least-squares minimization,, , ().   Google Scholar

[1]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068

[2]

Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223

[3]

Jinyan Fan. On the Levenberg-Marquardt methods for convex constrained nonlinear equations. Journal of Industrial & Management Optimization, 2013, 9 (1) : 227-241. doi: 10.3934/jimo.2013.9.227

[4]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[5]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199

[6]

Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25

[7]

Johann Baumeister, Barbara Kaltenbacher, Antonio Leitão. On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations. Inverse Problems & Imaging, 2010, 4 (3) : 335-350. doi: 10.3934/ipi.2010.4.335

[8]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070

[9]

Petr Knobloch. Error estimates for a nonlinear local projection stabilization of transient convection--diffusion--reaction equations. Discrete & Continuous Dynamical Systems - S, 2015, 8 (5) : 901-911. doi: 10.3934/dcdss.2015.8.901

[10]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61

[11]

Yanfei Lu, Qingfei Yin, Hongyi Li, Hongli Sun, Yunlei Yang, Muzhou Hou. Solving higher order nonlinear ordinary differential equations with least squares support vector machines. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1481-1502. doi: 10.3934/jimo.2019012

[12]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001

[13]

Basim A. Hassan. A new type of quasi-newton updating formulas based on the new quasi-newton equation. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 227-235. doi: 10.3934/naco.2019049

[14]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[15]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333

[16]

Enrique Fernández-Cara, Arnaud Münch. Numerical null controllability of semi-linear 1-D heat equations: Fixed point, least squares and Newton methods. Mathematical Control & Related Fields, 2012, 2 (3) : 217-246. doi: 10.3934/mcrf.2012.2.217

[17]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[18]

Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048

[19]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117

[20]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122

 Impact Factor: 

Metrics

  • PDF downloads (245)
  • HTML views (0)
  • Cited by (39)

Other articles
by authors

[Back to Top]