Recent advances in numerical methods for nonlinear equations andnonlinear least squares

Ya-Xiang Yuan

doi:10.3934/naco.2011.1.15

Article Contents

2011, Volume 1, Issue 1: 15-34. Doi: 10.3934/naco.2011.1.15

This issue Previous Article On methods for solving nonlinear semidefinite optimization problems Next Article CVaR-based formulation and approximation method for stochastic variational inequalities

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

Ya-Xiang Yuan^1,

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

Received: May 31, 2010

Revised: August 31, 2010

Published: January 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65K10; Secondary: 90C05.

Citation:

Related Papers

Cited by

References

[1]	J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.doi: 10.1093/imanum/8.1.141.
[2]	S. Bellavia, C. Cartis, N. I. M. Gould, B. Morini and Ph. 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.
[3]	L. Bergamaschi, I. Moret and G. Zilli, Inexact quasi-Newton methods for sparse systems of nonlinear equations, Future Generation Computer Systems, 18 (2001), 41-53.doi: 10.1016/S0167-739X(00)00074-1.
[4]	E. G. Birgin, N. Krejic and J. M. Martinez, Globally convergent inexact quasi-Newton methods for solving nonlinear systems, Numerical Algorithms, 32 (2003), 249-260.doi: 10.1023/A:1024013824524.
[5]	A. Bouaricha and J. J. Moré, Impact of Partial Separability on Large-Scale Optimization, Computational Optimization and Applications, 7 (1997), 27-40.doi: 10.1023/A:1008628114432.
[6]	M. H. Cheng, "Quasi-Newton Type Methods for Solving Large-Scale Problems,'' Ph.D. thesis, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010.
[7]	M. H. Cheng and Y. H. Dai, Sparse two-sided rank-one updates for nonlinear equations, Science in China, Ser. A., 53 (2010), 1-10.doi: 10.1007/s11425-010-4056-x.
[8]	A. R. Conn, N. J. M. Gould and Ph. L. Toint, "Trust-Region Methods," MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2000.
[9]	J. E. Dennis Jr. and J. J. Moré, Quasi-Newton methods, motivation and theory, SIAM Review, 19 (1977), 46-89.doi: 10.1137/1019005.
[10]	J. E. Dennis and R. B. Schnabel, "Numerical Methods for Unconstrained Optimization and Nonlinear Equations," SIAM, Philadelphia, 1993.
[11]	J. Y. Fan and Y. X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23-39.doi: 10.1007/s00607-004-0083-1.
[12]	J. Y. Fan and Y. X. Yuan, Regularized Newton method with correction for monotone nonlinear equations and its application, Report, AMSS, CAS, Beijing, 2010.
[13]	R. Fletcher, A model algorithm for composite NDO problem, Math. Program., 17 (1982), 67-76.
[14]	R. Fletcher, "Practical Methods of Optimization," Second Edition, John Wiley and Sons, 1987.
[15]	R. Fletcher and C. Xu, Hybrid methods for nonlinear least squares, IMA J. Numerical Analysis, 7 (1987), 371-389.doi: 10.1093/imanum/7.3.371.
[16]	G. H. Golub and V. Pereyra, The differentiation of pseudo-inverses and nonlinear least squares whose variables separable, SIAM J. Numer. Anal, 10 (1973), 413-432.doi: 10.1137/0710036.
[17]	G. H. Golub and V. Pereyra, Separable nonlinear least squares: the variable projection method and applications, Inverse Problems, 19 (2003), 1-26.doi: 10.1088/0266-5611/19/2/201.
[18]	G. H. Golub and C. F. Van Loan, "Matrix Computations,'' 3rd Edition, Johns Hopkins University Press, Baltimore and London, 1996.
[19]	N. I. M. Gould, D. Orban and Ph. L. Toint, Numerical methods for large-scale nonlinear optimization, Acta Numerica, 299-361, 2005.doi: 10.1017/S0962492904000248.
[20]	N. I. M. Gould and Ph. L. Toint, FILTRANE, a Fortran 95 filter-trust-region package for solving nonlinear least-squares and nonlinear feasibility problems, ACM Transactions on Mathematical Software (TOMS), 33 (2007), 3-25.doi: 10.1145/1206040.1206043.
[21]	A. Griewank, "Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation," Frontiers in Applied Mathematics, Vol 19, SIAM, Philadelphia, PA, 2000.
[22]	A. Griewank and A. Walther, On constrained optimization by adjoint based quasi-Newton methods, Optimizaiton Methods and Software, 17 (2002), 869-889.doi: 10.1080/1055678021000060829.
[23]	L. Kaufman, A variable projection method for solving separable nonlinear least squares problems, BIT, 15 (1975), 49-57.doi: 10.1007/BF01932995.
[24]	C.T. Kelley, "Iterative Methods for Linear and Nonlinear Equations," SIAM, Philadelphia, 1995.
[25]	C. T. Kelley, "Solving Nonlinear Equations with Newton's Method," Fundamentals of Algorithms Series, SIAM, Philadelphia, 2003.
[26]	C. Kanzow, N. Yamashita and M. Fukushima, Levenberg-Marquardt methods with storng local convergence properties for solving nonlinear equations with convex constraints, J. Comp. Appl. Math., 173 (2005), 321-343.
[27]	W. La Cruz and M. Raydan, Nonmonotone spectral methods for large-scale nonlinear sysstems, Optimization Methods and Software, 18 (2003), 583-599.doi: 10.1080/10556780310001610493.
[28]	W. La Cruz, J. M. Martinez and M. Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comp., 75 (2006), 1429-1448.doi: 10.1090/S0025-5718-06-01840-0.
[29]	D. H. Li and M. Fukushima, A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J. Numer. Anal., 37 (1999), 152-172.doi: 10.1137/S0036142998335704.
[30]	D. H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optimizaiton Methods and Software, 13 (2000), 181-201.doi: 10.1080/10556780008805782.
[31]	X. Liu and Y. X. Yuan, On the separable nonlinear least squares problems, J. Comput. Math., 26 (2008), 390-403.
[32]	J. M. Martinez, A quasi-Newton method with modification of one column per iteration, Computing, 33 (1984), 353-362.
[33]	E. Mizutani and J. W. Demmel, On structure-exploiting trust-region regularized nonlinear least squares algorithms for neural-network learning, Neural Networks, 16 (2003), 745-753.doi: 10.1016/S0893-6080(03)00085-6.
[34]	J. J. Moré, The Levenberg-Marquardt algorithm: implementation and theory, in "Lecture Notes in Mathematics 630: Numerical Analysis"(eds. G.A. Watson), Springer-Verlag, Berlin, 1978, pp. 105-116.
[35]	J. J. Moré, Recent developments in algorithms and software for trust region methods, in "Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, 1983)"(eds. A. Bachem, M. Grötschel and B. Korte), pp. 258-287.
[36]	J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Compute., 4 (1983), 553-572.doi: 10.1137/0904038.
[37]	Yu. Nesterov, Modified Gauss-Newton scheme with worst-case grarantees for global performance, Optimization Methods and Sofware, 22 (2007), 469-483.doi: 10.1080/08927020600643812.
[38]	J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, New York, 1999.doi: 10.1007/b98874.
[39]	J. M. Ortega and W. C. Rheinboldt, "Iterative Solution of Nonlinear Equations in Several Variables," Academic Press, New York and London, 1970.
[40]	M. J. D. Powell, A new algorithm for unconstrained optimization, in "Nonlinear Programming"(eds. J.B. Rosen, O.L. Mangasarian and K. Ritter), pp. 31-65, Academic Press, New York, 1970.
[41]	M. J. D. Powell, A method for minimizing a sum of squares of non-linear functions without calculating derivatives, The Computer J., 7 (1965), 303-307.
[42]	M. J. D. Powell, A hybrid method for nonlinear equations, in "Numerical Methods for Nonlinear Algebraic Equations"(eds. P. Robinowtiz), Gordon and Breach, London, 1970, pp. 87-114.
[43]	M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in "Numerical Analysis"(eds. G.A. Watson), Springer, Berlin, 1978, pp. 144-157.doi: 10.1007/BFb0067703.
[44]	M. J. D. Powell and Y. X. Yuan, Conditions for superlinear convergence in $l_1$ and $l_\infty$ solutions of overdetermined nonlinear equations, IMA J. Numerical Analysis, 4 (1984), 241-251.doi: 10.1093/imanum/4.2.241.
[45]	A. Ruhe and P. Å. Wedin, Algorithms for separable nonlinear least squares problems, SIAM Review, 22 (1980), 318-337.doi: 10.1137/1022057.
[46]	Y. Saad, "Iterative Methods for Sparse Linear Systems," SIAM, New York, 2003.doi: 10.1137/1.9780898718003.
[47]	S. Schlenkrich, A. Griewank and A. Walther, On the local convergence of adjoint Broyden methods, Math. Program., 121 (2010), 221-247.doi: 10.1007/s10107-008-0232-y.
[48]	K. Schittkowski, Solving nonlinear least squares problems by a general purpose SQP-method, 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.
[49]	K. Schittkowski, "Numerical Data Fitting in Dynamical Systems," Applied Optimization Vol. 77, Kluwer Academic Publishers, Dordrecht, 2002.
[50]	L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp., 24 (1970), 27-30.doi: 10.1090/S0025-5718-1970-0258276-9.
[51]	T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numerical Analysis, 20 (1983), 626-637.doi: 10.1137/0720042.
[52]	J. Stoer and Y. X. Yuan, A subspace study on conjugate gradient algorithms, Z. Angew. Math. Mech., 75 (1995), 69-77.doi: 10.1002/zamm.19950750118.
[53]	W. Y. Sun and Y. X. Yuan, "Optimization Theory and Mehtods: Nonlinear Programming," Springer Series on Optimization and Its Application, Vol. 1, Springer, 2006.
[54]	Ph. L. Toint, On sparse and sysmmetric matrix updating subject to a linear equation, Mathematics of Computation, 31 (1977), 954-961.doi: 10.1090/S0025-5718-1977-0455338-4.
[55]	Ph. L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, in "Sparse Matrices and Their Uses"( eds. I. Duff), Academic Press, 1981, pp. 57-88.
[56]	Ph. L. Toint, On large scale nonlinear least squares calculations, SIAM J. Sci. Stat. Comput., 8 (1987), 416-435.doi: 10.1137/0908042.
[57]	Z. H. Wang and Y. X. Yuan, A subspace implementation of quasi-Newton trust region methods for unconstrained optimization, Numerische Mathematik, 104 (2006), 241-269.doi: 10.1007/s00211-006-0021-6.
[58]	N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method , Computing, (Supplement) 15 (2001), 237-249.
[59]	Y. X. Yuan, Trust region algorithms for nonlinear equations, Information, 1 (1998), 7-20.
[60]	Y. X. Yuan, On the truncated conjugate gradient method, Math. Program., 87 (2000), 561-573.doi: 10.1007/s101070050012.
[61]	Y. X. Yuan, Subspace techniques for nonlinear optimization, 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.
[62]	Y. X. Yuan, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optimization and Engineering, 10 (2009), 207-218.doi: 10.1007/s11081-008-9064-0.
[63]	H. C. Zhang, A. R. Conn and K. Scheinberg, A derivative-free algorithm for the least-squares minimization, http://www.math.lsu.edu/ hozhang/zhcpaper.html.
[64]	H. C. Zhang, A. R. Conn and K. Scheinberg, On the local convergence of a derivative-free algorithm for least-squares minimization, http://www.math.lsu.edu/ hozhang/zhcpaper.html.