Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A relaxed nonmonotone adaptive trust region method for solving unconstrained optimization problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we present a new relaxed nonmonotone trust region method with adaptive radius for solving unconstrained optimization problems. The proposed method combines a relaxed nonmonotone technique with a modified version of the adaptive trust region strategy proposed by Shi and Guo (J Comput Appl Math 213:509–520, 2008). Under some suitable and standard assumptions, we establish the global convergence property as well as the superlinear convergence rate for the new method. Numerical results on some test problems show the efficiency and effectiveness of the new proposed method in practice.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ahookhosh, M., Amini, K.: A nonmonotone trust region method with adaptive radius for unconstrained optimization. Comput. Math. Appl. 60, 411–422 (2010)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  3. Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10(1), 147–161 (2008)

    MATH  MathSciNet  Google Scholar 

  4. Chamberlain, R.M., Powell, M.J.D., Lemarechal, C., Pedersen, H.C.: The watchdog technique for forcing convergence in algorithm for constrained optimization. Math. Program. Stud. 16, 1–17 (1982)

    MATH  MathSciNet  Google Scholar 

  5. Conn, A., Gould, N., Toint, PhL: Trust Region Method. SIAM, Philadelphia (2000)

    Book  Google Scholar 

  6. Cui, Z., Wu, B.: A new modified nonmonotone adaptive trust region method for unconstrained optimization. Comput. Optim. Appl. 53, 795–806 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  7. Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112(2), 315–330 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. Deng, N.Y., Xiao, Y., Zhou, F.J.: Nonmonotonic trust region algorithm. J. Optim. Theory Appl. 76, 259–285 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dolan, E., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  10. Fan, J.Y., Yuan, Y.X.: A new trust region algorithm with trust region radius converging to zero. In: Proceedings of the 5th International Conference on Optimization: Techniques and Applications [C], Hong Kong (2001)

  11. Fu, J.H., Sun, W.Y.: Nonmonotone adaptive trust-region method for unconstrained optimization problems. Appl. Math. Comput. 63, 489–504 (2005)

    Article  MathSciNet  Google Scholar 

  12. Gertz, E.M.: A quasi-Newton trust-region method. Math. Program. 100, 447–470 (2004)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  14. Grippo, L., Lamparillo, F., Lucidi, S.: A truncated Newton method with nonmonotone line search for unconstrained optimization. J. Optim. Theory Appl. 60(3), 401–419 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  15. Lin, C.J., Moré, J.J.: Newton’s method for large bound-constrained optimization problems. SIAM J. Optim. 9(4), 1100–1127 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  16. Moré, J.J., Grabow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981)

    Article  MATH  Google Scholar 

  17. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, NewYork (2006)

    MATH  Google Scholar 

  18. Nocedal, J., Yuan, Y.: Combining trust region and line search techniques. In: Yuan, Y. (ed.) Advances in Nonlinear Programming, pp. 153–175. Kluwer Academic Publishers, Dordrecht (1996)

    Google Scholar 

  19. Panier, E.R., Tits, A.L.: Avoiding the Maratos effect by means of a nonmonotone linesearch. SIAM J. Numer. Anal. 28, 1183–1195 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  20. Powell, M.J.D.: On the global convergence of trust region algorithms for unconstrained optimization. Math. Program. 29, 297–303 (1984)

    Article  MATH  Google Scholar 

  21. Sang, Z., Sun, Q.: Aself-adaptive trust region method with linesearch based on a simple subproblem model. J. Comput. Appl. Math. 232, 514–522 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  22. Sartenaer, A.: Automatic determination of an initial trust region in nonlinear programming. SIAM J. Sci. Comput. 18(6), 1788–1803 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  23. Shi, Z.J., Guo, J.H.: A new trust region method for unconstrained optimization. J. Comput. Appl. Math. 213, 509–520 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Shi, Z.J., Wang, H.Q.: A new self-adaptive trust region method for unconstrained optimization. Technical Report, College of Operations Research and Management, Qufu Normal University (2004)

  25. Toint, PhL: An assessment of nonmonotone linesearch technique for unconstrained opti-mization. SIAM J. Sci. Comput. 17, 725–739 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  26. Toint, PhL: Non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77, 69–94 (1997)

    MATH  MathSciNet  Google Scholar 

  27. Xiao, Y., Chu, E.K.W.: Nonmonotone trust region methods. Technical Report 95/17, Monash University, Clayton, Australia (1995)

  28. Xiao, Y., Zhou, F.J.: Nonmonotone trust region methods with curvilinear path in uncon-strained optimization. Computing 48, 303–317 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  29. Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14(4), 1043–1056 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  30. Zhang, X.S., Zhang, J.L., Liao, L.Z.: An adaptive trust region method and its convergence. Sci. China 45, 620–631 (2002)

    MATH  MathSciNet  Google Scholar 

  31. Zhang, X.S., Zhang, J.L., Liao, L.Z.: A nonmonotone adaptive trust region method and its convergence. Comput. Math. Appl. 45, 1469–1477 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  32. Zhou, F., Xiao, Y.: A class of nonmonotone stabilization trust region methods. Computing 53(2), 119–136 (1994)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the Research Councils of K.N. Toosi University of Technology and the SCOPE research center for supporting this research. The authors would also like to appreciate the anonymous referees for generously providing us insightful comments which significantly improved the quality of the paper.

Author information

Authors and Affiliations

  1. Faculty of Mathematics, K.N. Toosi University of Technology, P.O. Box 16315-1618, Tehran, Iran

    M. Reza Peyghami

  2. Scientific Computations in Optimization and Systems Engineering (SCOPE), K.N. Toosi University of Technology, Tehran, Iran

    M. Reza Peyghami & D. Ataee Tarzanagh

Authors
  1. M. Reza Peyghami
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Ataee Tarzanagh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Reza Peyghami.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (docx 22 KB)

Appendix

Appendix

Proof of Lemma 3.6

We proceed by induction on \(L\). For \(L=0\), using Lemma 3.3, we have

$$\begin{aligned} f_{k_r } \le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_r -1} \left( {1+\varphi _i } \right) -\omega _{k_r -1} \le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_r -1} \left( {1+\varphi _i } \right) -\tilde{\omega }_0 ,\quad r=0,1,\ldots ,M-1, \end{aligned}$$

where \(\tilde{\omega }_0 =\mathop {\min }\nolimits _{0\le r\le M-1} \omega _{k_r } \). Suppose that (24) holds for \(L=t\) (the induction hypothesis). For \(L=t+1\), we show that

For this purpose, we proceed by induction on \(r\). From (19), for \(r=0\), we have:

$$\begin{aligned} f_{k_{(t+1)M} }&\le \left( {1+\varphi _{k_{(t+1)M} -1} } \right) R_{k_{(t+1)M} -1} -\omega _{k_{(t+1)M} -1}\\&\le \left( {1+\varphi _{k_{(t+1)M} -1} } \right) f_{l(k_{(t+1)M} -1)} -\omega _{k_{(t+1)M} -1} . \end{aligned}$$

Due to the definition of \(f_{l(j)} \) in Remark 2.1, we have

Thus, from the latter inequality, we have:

Now, using (31), (32), the induction hypothesis (over \(L\)) and the fact that \(l(k_{(t+1)M} -1)\le k_{(t+1)M} -1\), we have

$$\begin{aligned} f_{k_{(t+1)M} }&\le \left( {1+\varphi _{k_{(t+1)M} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{l(k_{tM+M-1} )-1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega }_i } \right\} -\omega _{k_{(t+1)M} -1} \\&\le \left( {1+\varphi _{k_{(t+1)M} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{l(k_{(t+1)M} -1)-1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega }_i } \right\} -\omega _{k_{(t+1)M} -1} \\&\le \left( {1+\varphi _{k_{(t+1)M} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{(t+1)M} -2} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega } _i } \right\} -\omega _{k_{(t+1)M} -1} \\&= \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{(t+1)M} -1} \left( {1+\varphi _i } \right) -\left( {1+\varphi _{k_{(t+1)M} -1} } \right) \mathop \sum \limits _{i=0}^t \tilde{\omega } _i -\omega _{k_{(t+1)M} -1} \\&\le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{(t+1)M} -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega } _i -\omega _{k_{(t+1)M} -1} \\&\le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{(t+1)M} -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega } _i -\tilde{\omega } _{t+1} , \end{aligned}$$

where the second inequality is obtained from the fact that \(\varphi _i \ge 0\). Assume that (30) holds for \(r=j\le M-2\) (induction hypothesis). For \(r=j+1\), from (21), we have:

$$\begin{aligned} f_{k_{\left( {t+1} \right) M+j+1} }&\le \left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) R_{k_{\left( {t+1} \right) M+j+1} -1} -\omega _{k_{\left( {t+1} \right) M+j+1} -1}\\&\le \left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) f_{l\left( {k_{\left( {t+1} \right) M+j+1} -1} \right) } -\omega _{k_{\left( {t+1} \right) M+j+1} -1} . \end{aligned}$$

From Remark 2.1, we have

$$\begin{aligned} f_{l\left( {k_{\left( {t+1} \right) M+j} } \right) } =f_{l\left( {k_{\left( {t+1} \right) M+j+1} -1} \right) .} \end{aligned}$$

Moreover, as \(l\left( {k_{\left( {t+1} \right) M+j} } \right) \le l\left( {k_{\left( {t+1} \right) M+j+1} -1} \right) \le k_{\left( {t+1} \right) M+j+1} -1\), then from induction hypothesis (over \(r\)), we obtain:

$$\begin{aligned} f_{k_{\left( {t+1} \right) M+j+1} }&\le \left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{l\left( {k_{\left( {t+1} \right) M+j} } \right) -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega }_i } \right\} -\omega _{k_{\left( {t+1} \right) M+j+1} -1} \\&\le \left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{l\left( {k_{\left( {t+1} \right) M+j+1} -1} \right) -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega }_i } \right\} -\omega _{k_{\left( {t+1} \right) M+j+1} -1} \\&\le \left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) \left\{ {\left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{\left( {t+1} \right) M+j+1} -2} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^t \tilde{\omega }_i } \right\} -\omega _{k_{\left( {t+1} \right) M+j+1} -1} \\&\le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{\left( {t+1} \right) M+j+1} -1} \left( {1+\varphi _i } \right) -\left( {1+\varphi _{k_{\left( {t+1} \right) M+j+1} -1} } \right) \mathop \sum \limits _{i=0}^t \tilde{\omega }_i -\omega _{k_{\left( {t+1} \right) M+j+1} -1} \\&\le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{\left( {t+1} \right) M+j+1} -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^{t} \tilde{\omega }_i-\tilde{\omega }_{t+1}\\&\le \left| {f_0 } \right| \mathop \prod \limits _{i=0}^{k_{\left( {t+1} \right) M+j+1} -1} \left( {1+\varphi _i } \right) -\mathop \sum \limits _{i=0}^{t+1} \tilde{\omega }_i . \end{aligned}$$

This completes the proof of the lemma. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Reza Peyghami, M., Ataee Tarzanagh, D. A relaxed nonmonotone adaptive trust region method for solving unconstrained optimization problems. Comput Optim Appl 61, 321–341 (2015). https://doi.org/10.1007/s10589-015-9726-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9726-8

Keywords

Search

Navigation