×

zbMATH — the first resource for mathematics

A new nonmonotone line-search trust-region approach for nonlinear systems. (English) Zbl 1416.65144
Summary: This paper introduces a new derivative-free trust-region algorithm for solving nonlinear systems, based on a new nonmonotone technique and an adaptive radius strategy. It is shown that we can generate the small (large) steps and radii in the cases where iterations are near (far away from) the optimizer. Such a nonmonotone strategy is embedded into the trust region framework and Armijo line search to face with problems which have the narrow curved valley. To prevent resolving the trust-region subproblem, the nonmonotone Armijo line search is used whenever iterations are unsuccessful. In each iteration, the adaptive radius strategy is constructed based on the norm of the best function values. The global and q-quadratic rate of convergence of the new algorithm is proved. Computational results are reported.

MSC:
65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
Software:
CoDoSol; minpack; STRSCNE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahookhosh, M.; Amini, K., An efficient nonmonotone trust-region method for unconstrained optimization, Numer Algorithms, 59, 523-540, (2012) · Zbl 1243.65066
[2] Ahookhosh, M.; Amini, K.; Peyghami, MR, A nonmonotone trust-region line search method for large-scale unconstrained optimization, Appl Math Model, 36, 478-487, (2012) · Zbl 1236.90077
[3] Ahookhosh, M.; Amini, K.; Kimiaei, M., A globally convergent trust-region method for large-scale symmetric nonlinear systems, Numer Funct Anal Optim, 36, 830-855, (2015) · Zbl 1330.65074
[4] Ahookhosh, M.; Esmaeili, H.; Kimiaei, M., An effective trust-region-based approach for symmetric nonlinear systems, Int J Comput Math, 90, 671-690, (2013) · Zbl 1273.90197
[5] Amini, K.; Shiker, Mushtak AK; Kimiaei, M., A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations, 4OR-Q J Oper Res, 4, 132-152, (2016) · Zbl 1342.90178
[6] Amini, K.; Esmaeili, H.; Kimiaei, M., A nonmonotone trust-region-approach with nonmonotone adaptive radius for solving nonlinear systems, Iran J Numer Anal Optim, 6, 101-119, (2016) · Zbl 1343.65057
[7] Bellavia, S.; Macconi, M.; Morini, B., STRSCNE: a scaled trust-region solver for constrained nonlinear equations, Comput Optim Appl, 28, 31-50, (2004) · Zbl 1056.90128
[8] Bellavia, S.; Macconi, M.; Pieraccini, S., Constrained Dogleg methods for nonlinear systems with simple bounds, Comput Optim Appl, 53, 771-794, (2012) · Zbl 1262.90163
[9] Bouaricha, A.; Schnabel, RB, Tensor methods for large sparse systems of nonlinear equations, Math Progr, 82, 377-400, (1998) · Zbl 0951.65046
[10] Broyden, CG, The convergence of an algorithm for solving sparse nonlinear systems, Math Comput, 25, 285-294, (1971) · Zbl 0227.65038
[11] Buhmiler, S.; Krejić, N.; Lužanin, Z., Practical quasi-Newton algorithms for singular nonlinear systems, Numer Algorithm, 55, 481-502, (2010) · Zbl 1201.65076
[12] Chamberlain, RM; Powell, MJD; Lemaréchal, C.; Pedersen, HC, The watchdog technique for forcing convergence in algorithms for constrained optimization, Math Progr Study, 16, 1-17, (1982) · Zbl 0477.90072
[13] Conn AR, Gould NIM, Toint PHL (2000) Trust-region methods. Society for Industrial and Applied Mathematics, SIAM, Philadelphia
[14] Dedieu, JP; Shub, M., Newton’s method for overdetermined systems of equations, Math Comput, 69, 1099-1115, (2000) · Zbl 0949.65061
[15] Esmaeili, H.; Kimiaei, M., A new adaptive trust-region method for system of nonlinear equations, Appl Math Model, 38, 3003-3015, (2014) · Zbl 1427.65080
[16] Esmaeili, H.; Kimiaei, M., An efficient adaptive trust-region method for systems of nonlinear equations, Int J Comput Math, 92, 151-166, (2015) · Zbl 1308.90167
[17] Esmaeili, H.; Kimiaei, M., A trust-region method with improved adaptive radius for systems of nonlinear equations, Math Meth Oper Res, 83, 109-125, (2016) · Zbl 1333.90126
[18] Deng, NY; Xiao, Y.; Zhou, FJ, Nonmonotonic trust region algorithm, J Optim Theory Appl, 26, 259-285, (1993) · Zbl 0797.90088
[19] Dennis, JE, On the convergence of Broyden’s method for nonlinear systems of equations, Math Comput, 25, 559-567, (1971) · Zbl 0277.65030
[20] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Progr, 91, 201-213, (2002) · Zbl 1049.90004
[21] Fan, JY, Convergence rate of the trust region method for nonlinear equations under local error bound condition, Comput Optim Appl, 34, 215-227, (2005) · Zbl 1121.65054
[22] Fan, JY, An improved trust region algorithm for nonlinear equations, Comput Optim Appl, 48, 59-70, (2011) · Zbl 1230.90178
[23] Fan, JY; Pan, JY, A modified trust region algorithm for nonlinear equations with new updating rule of trust region radius, Int J Comput Math, 87, 3186-3195, (2010) · Zbl 1207.65055
[24] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J Numer Anal, 23, 707-716, (1986) · Zbl 0616.65067
[25] Fasano, G.; Lampariello, F.; Sciandrone, M., A truncated nonmonotone Gauss-Newton method for large-scale nonlinear least-squares problems, Comput Optim Appl, 34, 343-358, (2006) · Zbl 1122.90094
[26] Gertz, EM, A quasi-Newton trust-region method, Math Progr Ser A, 100, 447-470, (2004) · Zbl 1068.90108
[27] Gertz EM (1999) Combination trust-region line-search methods for unconstrained optimization, University of California San Diego
[28] Gill, PhE; Murray, W., Algorithms for the Solution of the Nonlinear Least-Squares Problem, SIAM J Numer Anal, 15, 977-992, (1978) · Zbl 0401.65042
[29] Gill PhE, Wright MH (2001) Department of Mathematics University of California San Diego, Course Notes for Numerical Nonlinear Optimization
[30] Griewank, A., The global convergence of Broyden-like methods with a suitable line search, J Aust Math Soc, Ser B, 28, 75-92, (1986) · Zbl 0596.65034
[31] Grippo, L.; Sciandrone, M., Nonmonotone derivative-free methods for nonlinear equations, Comput Optim Appl, 37, 297-328, (2007) · Zbl 1180.90310
[32] Gu, GZ; Li, DH; Qi, L.; Zhou, SZ, Descent directions of Quasi-Newton methods for symmetric nonlinear equations, SIAM J Numer Anal, 40, 1763-1774, (2003) · Zbl 1047.65032
[33] Kimiaei, M., A new class of nonmonotone adaptive trust-region methods for nonlinear equations with box constraints, Calcolo, 54, 769-812, (2017) · Zbl 1373.90151
[34] Kimiaei, M., Nonmonotone self-adaptive Levenberg-Marquardt approach for solving systems of nonlinear equations, Numer Funct Anal Optim, 39, 47-66, (2018) · Zbl 1390.90517
[35] La Cruz W, Venezuela C, Martínez JM, Raydan M (July 2004) Spectral residual method without gradient information for solving large-scale nonlinear systems of equations: theory and experiments, Technical Report RT-04-08
[36] Levenberg, K., A method for the solution of certain non-linear problems in least squares, Quart Appl Math, 2, 164-166, (1944) · Zbl 0063.03501
[37] Li Q, Li DH (2011) A class of derivative-free methods for large-scale nonlinear monotone equations. IMA Journal of Numerical Analysis 1-11
[38] Li, D.; Fukushima, M., A global and superlinear convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J Numer Anal, 37, 152-172, (1999) · Zbl 0946.65031
[39] Lukšan, L.; Vlček, J., Truncated trust region methods based on preconditioned iterative subalgorithms for large sparse systems of nonlinear equations, J Optim Theory Appl, 95, 637-658, (1997) · Zbl 0902.90146
[40] Marquardt, DW, An algorithm for least-squares estimation of nonlinear parameters, SIAM J Appl Math, 11, 431-441, (1963) · Zbl 0112.10505
[41] Martinez, JM, A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J Numer Anal, 27, 1034-1049, (1990) · Zbl 0702.65053
[42] Moré, JJ; Garbow, BS; Hillström, KE, Testing unconstrained optimization software, ACM Trans Math Softw, 7, 17-41, (1981) · Zbl 0454.65049
[43] Nocedal J, Wright SJ (2006) Numerical optimization. Springer, NewYork
[44] Nocedal J, Yuan Ya Xiang (1998) Combining trust-region and line-search techniques. Optimization Technology Center mar OTC 98/04
[45] Ortega JM, Rheinboldt WC (1970) Iterative solution of nonlinear equations in several variables. Academic Press, New York
[46] Powell, MJD; Rosen, JB (ed.); Mangasarian, OL (ed.); Ritter, K. (ed.), A new algorithm for unconstrained optimization, (1970), Cambridge
[47] Powell, MJD; Mangasarian, OL (ed.); Meyer, RR (ed.); Robinson, SM (ed.), Convergence properties of a class of minimization algorithms, 1-27, (1975), Cambridge
[48] Schnabel, RB; Frank, PD, Tensor methods for nonlinear equations, SIAM J Numer Anal, 21, 815-843, (1984) · Zbl 0562.65029
[49] Thomas SW (1975) Sequential estimation techniques for quasi-Newton algorithms, Cornell University
[50] Toint, PhL, Numerical solution of large sets of algebraic nonlinear equations, Math Comput, 46, 175-189, (1986) · Zbl 0614.65058
[51] Toint PhL (1982) Towards an efficient sparsity exploiting Newton method for minimization, Sparse Matrices and Their Uses Academic Press NewYork I. S. Duff 57-87
[52] Tong, XJ; Qi, L., On the convergence of a trust-region method for solving constrained nonlinear equations with degenerate solutions, J Optim Theory Appl, 123, 187-211, (2004) · Zbl 1069.65055
[53] Yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, Computing, 15, 239-249, (2001) · Zbl 1001.65047
[54] Yuan, GL; Lu, XW; Wei, ZX, BFGS trust-region method for symmetric nonlinear equations, J Comput Appl Math, 230, 44-58, (2009) · Zbl 1168.65026
[55] Yuan, GL; Meng, Z.; Li, Y., A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, J Optim Theory Appl, 168, 129-152, (2016) · Zbl 1332.65081
[56] Yuan, GL; Wei, ZX; Lu, S., Limited memory BFGS method with backtracking for symmetric nonlinear equations, Math Comput Model, 54, 367-377, (2011) · Zbl 1225.65056
[57] Yuan, GL; Wei, ZX; Lu, XW, A BFGS trust-region method for nonlinear equations, Computing, 92, 317-333, (2011) · Zbl 1241.65049
[58] Yuan, GL; Zhang, M., A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations, J Comput Appl Math, 286, 186-95, (2015) · Zbl 1316.90038
[59] Yuan, GL, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optim Eng, 10, 207-218, (2009) · Zbl 1171.65040
[60] Yuan, Y., Trust region algorithm for nonlinear equations, Information, 1, 7-21, (1998)
[61] Yuan, Y., Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numer Algebra, Control Optim, 1, 15-34, (2011) · Zbl 1226.65045
[62] Zhang, HC; Hager, WW, A nonmonotone line search technique for unconstrained optimization, SIAM J Optim, 14, 1043-1056, (2004) · Zbl 1073.90024
[63] Zhang, J.; Wang, Y., new trust region method for nonlinear equations, Math Methods Oper Res, 58, 283-298, (2003) · Zbl 1043.65072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.