Skip to main content
SpringerLink
Log in

A new nonmonotone line-search trust-region approach for nonlinear systems

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Ahookhosh M, Amini K (2012) An efficient nonmonotone trust-region method for unconstrained optimization. Numer Algorithms 59:523–540

    Article  Google Scholar 

  • Ahookhosh M, Amini K, Peyghami MR (2012) A nonmonotone trust-region line search method for large-scale unconstrained optimization. Appl Math Model 36:478–487

    Article  Google Scholar 

  • Ahookhosh M, Amini K, Kimiaei M (2015) A globally convergent trust-region method for large-scale symmetric nonlinear systems. Numer Funct Anal Optim 36:830–855

    Article  Google Scholar 

  • Ahookhosh M, Esmaeili H, Kimiaei M (2013) An effective trust-region-based approach for symmetric nonlinear systems. Int J Comput Math 90:671–690

    Article  Google Scholar 

  • Amini K, Shiker Mushtak AK, Kimiaei M (2016) A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations. 4OR-Q J Oper Res 4(2):132–152

    Google Scholar 

  • Amini K, Esmaeili H, Kimiaei M (2016) A nonmonotone trust-region-approach with nonmonotone adaptive radius for solving nonlinear systems. Iran J Numer Anal Optim 6(1):101–119

    Google Scholar 

  • Bellavia S, Macconi M, Morini B (2004) STRSCNE: a scaled trust-region solver for constrained nonlinear equations. Comput Optim Appl 28:31–50

    Article  Google Scholar 

  • Bellavia S, Macconi M, Pieraccini S (2012) Constrained Dogleg methods for nonlinear systems with simple bounds. Comput Optim Appl 53:771–794

    Article  Google Scholar 

  • Bouaricha A, Schnabel RB (1998) Tensor methods for large sparse systems of nonlinear equations. Math Progr 82:377–400

    Google Scholar 

  • Broyden CG (1971) The convergence of an algorithm for solving sparse nonlinear systems. Math Comput 25(114):285–294

    Article  Google Scholar 

  • Buhmiler S, Krejić N, Lužanin Z (2010) Practical quasi-Newton algorithms for singular nonlinear systems. Numer Algorithm 55:481–502

    Article  Google Scholar 

  • Chamberlain RM, Powell MJD, Lemaréchal C, Pedersen HC (1982) The watchdog technique for forcing convergence in algorithms for constrained optimization. Math Progr Study 16:1–17

    Article  Google Scholar 

  • Conn AR, Gould NIM, Toint PHL (2000) Trust-region methods. Society for Industrial and Applied Mathematics, SIAM, Philadelphia

  • Dedieu JP, Shub M (2000) Newton’s method for overdetermined systems of equations. Math Comput 69(231):1099–1115

    Article  Google Scholar 

  • Esmaeili H, Kimiaei M (2014) A new adaptive trust-region method for system of nonlinear equations. Appl Math Model 38(11–12):3003–3015

    Article  Google Scholar 

  • Esmaeili H, Kimiaei M (2015) An efficient adaptive trust-region method for systems of nonlinear equations. Int J Comput Math 92:151–166

    Article  Google Scholar 

  • Esmaeili H, Kimiaei M (2016) A trust-region method with improved adaptive radius for systems of nonlinear equations. Math Meth Oper Res 83:109–125

    Article  Google Scholar 

  • Deng NY, Xiao Y, Zhou FJ (1993) Nonmonotonic trust region algorithm. J Optim Theory Appl 26:259–285

    Article  Google Scholar 

  • Dennis JE (1971) On the convergence of Broyden’s method for nonlinear systems of equations. Math Comput 25(115):559–567

    Google Scholar 

  • Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Progr 91:201–213

    Article  Google Scholar 

  • Fan JY (2005) Convergence rate of the trust region method for nonlinear equations under local error bound condition. Comput Optim Appl 34:215–227

    Article  Google Scholar 

  • Fan JY (2011) An improved trust region algorithm for nonlinear equations. Comput Optim Appl 48(1):59–70

    Article  Google Scholar 

  • Fan JY, Pan JY (2010) A modified trust region algorithm for nonlinear equations with new updating rule of trust region radius. Int J Comput Math 87(14):3186–3195

    Article  Google Scholar 

  • Grippo L, Lampariello F, Lucidi S (1986) A nonmonotone line search technique for Newton’s method. SIAM J Numer Anal 23:707–716

    Article  Google Scholar 

  • Fasano G, Lampariello F, Sciandrone M (2006) A truncated nonmonotone Gauss–Newton method for large-scale nonlinear least-squares problems. Comput Optim Appl 34(3):343–358

    Article  Google Scholar 

  • Gertz EM (2004) A quasi-Newton trust-region method. Math Progr Ser A 100:447–470

    Google Scholar 

  • Gertz EM (1999) Combination trust-region line-search methods for unconstrained optimization, University of California San Diego

  • Gill PhE, Murray W (1978) Algorithms for the Solution of the Nonlinear Least-Squares Problem. SIAM J Numer Anal 15(5):977–992

    Article  Google Scholar 

  • Gill PhE, Wright MH (2001) Department of Mathematics University of California San Diego, Course Notes for Numerical Nonlinear Optimization

  • Griewank A (1986) The global convergence of Broyden-like methods with a suitable line search. J Aust Math Soc, Ser B 28:75–92

    Article  Google Scholar 

  • Grippo L, Sciandrone M (2007) Nonmonotone derivative-free methods for nonlinear equations. Comput Optim Appl 37:297–328

    Article  Google Scholar 

  • Gu GZ, Li DH, Qi L, Zhou SZ (2003) Descent directions of Quasi-Newton methods for symmetric nonlinear equations. SIAM J Numer Anal 40(5):1763–1774

    Article  Google Scholar 

  • Kimiaei M (2017) A new class of nonmonotone adaptive trust-region methods for nonlinear equations with box constraints. Calcolo 54(3):769–812

    Article  Google Scholar 

  • Kimiaei M (2018) Nonmonotone self-adaptive Levenberg–Marquardt approach for solving systems of nonlinear equations. Numer Funct Anal Optim 39(1):47–66

    Article  Google Scholar 

  • 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

  • Levenberg K (1944) A method for the solution of certain non-linear problems in least squares. Quart Appl Math 2:164–166

    Article  Google Scholar 

  • Li Q, Li DH (2011) A class of derivative-free methods for large-scale nonlinear monotone equations. IMA Journal of Numerical Analysis 1–11

  • Li D, Fukushima M (1999) A global and superlinear convergent Gauss–Newton-based BFGS method for symmetric nonlinear equations. SIAM J Numer Anal 37:152–172

    Article  Google Scholar 

  • Lukšan L, Vlček J (1997) Truncated trust region methods based on preconditioned iterative subalgorithms for large sparse systems of nonlinear equations. J Optim Theory Appl 95(3):637–658

    Article  Google Scholar 

  • Marquardt DW (1963) An algorithm for least-squares estimation of nonlinear parameters. SIAM J Appl Math 11:431–441

    Article  Google Scholar 

  • Martinez JM (1990) A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations. SIAM J Numer Anal 27(4):1034–1049

    Article  Google Scholar 

  • Moré JJ, Garbow BS, Hillström KE (1981) Testing unconstrained optimization software. ACM Trans Math Softw 7:17–41

    Article  Google Scholar 

  • Nocedal J, Wright SJ (2006) Numerical optimization. Springer, NewYork

    Google Scholar 

  • Nocedal J, Yuan Ya Xiang (1998) Combining trust-region and line-search techniques. Optimization Technology Center mar OTC 98/04

  • Ortega JM, Rheinboldt WC (1970) Iterative solution of nonlinear equations in several variables. Academic Press, New York

    Google Scholar 

  • Powell MJD (1970) A new algorithm for unconstrained optimization. In: Rosen JB, Mangasarian OL, Ritter K (eds) Nonlinear programming. Academic Press, Cambridge

    Google Scholar 

  • Powell MJD (1975) Convergence properties of a class of minimization algorithms. In: Mangasarian OL, Meyer RR, Robinson SM (eds) Nonlinear programming 2. Academic Press, Cambridge, pp 1–27

    Google Scholar 

  • Schnabel RB, Frank PD (1984) Tensor methods for nonlinear equations. SIAM J Numer Anal 21(5):815–843

    Article  Google Scholar 

  • Thomas SW (1975) Sequential estimation techniques for quasi-Newton algorithms, Cornell University

  • Toint PhL (1986) Numerical solution of large sets of algebraic nonlinear equations. Math Comput 46(173):175–189

    Article  Google Scholar 

  • 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

  • Tong XJ, Qi L (2004) On the convergence of a trust-region method for solving constrained nonlinear equations with degenerate solutions. J Optim Theory Appl 123(1):187–211

    Article  Google Scholar 

  • Yamashita N, Fukushima M (2001) On the rate of convergence of the Levenberg–Marquardt method. Computing 15:239–249

    Google Scholar 

  • Yuan GL, Lu XW, Wei ZX (2009) BFGS trust-region method for symmetric nonlinear equations. J Comput Appl Math 230:44–58

    Article  Google Scholar 

  • Yuan GL, Meng Z, Li Y (2016) A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations. J Optim Theory Appl 168:129–152

    Article  Google Scholar 

  • Yuan GL, Wei ZX, Lu S (2011) Limited memory BFGS method with backtracking for symmetric nonlinear equations. Math Comput Model 54:367–377

    Article  Google Scholar 

  • Yuan GL, Wei ZX, Lu XW (2011) A BFGS trust-region method for nonlinear equations. Computing 92(4):317–333

    Article  Google Scholar 

  • Yuan GL, Zhang M (2015) A three-terms Polak–Ribière–Polyak conjugate gradient algorithm for large-scale nonlinear equations. J Comput Appl Math 286:186–95

    Article  Google Scholar 

  • Yuan GL (2009) Subspace methods for large scale nonlinear equations and nonlinear least squares. Optim Eng 10:207–218

    Article  Google Scholar 

  • Yuan Y (1998) Trust region algorithm for nonlinear equations. Information 1:7–21

    Google Scholar 

  • Yuan Y (2011) Recent advances in numerical methods for nonlinear equations and nonlinear least squares. Numer Algebra, Control Optim 1(1):15–34

    Article  Google Scholar 

  • Zhang HC, Hager WW (2004) A nonmonotone line search technique for unconstrained optimization. SIAM J Optim 14(4):1043–1056

    Article  Google Scholar 

  • Zhang J, Wang Y (2003) new trust region method for nonlinear equations. Math Methods Oper Res 58:283–298

    Article  Google Scholar 

Download references

Acknowledgements

The first author acknowledges the financial support of the Doctoral Program “Vienna Graduate School on Computational Optimization” funded by Austrian Science Foundation under Project No W1260-N35.

Author information

Authors and Affiliations

  1. Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Vienna, Austria

    Morteza Kimiaei

  2. Department of Mathematics, Payame Noor University, PO BOX 19395–3697, Tehran, Iran

    Farzad Rahpeymaii

Authors
  1. Morteza Kimiaei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Farzad Rahpeymaii
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Morteza Kimiaei.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kimiaei, M., Rahpeymaii, F. A new nonmonotone line-search trust-region approach for nonlinear systems. TOP 27, 199–232 (2019). https://doi.org/10.1007/s11750-019-00497-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-019-00497-2

Keywords

Mathematics Subject Classification

Search

Navigation