A novel nonmonotone trust region method based on the Metropolis criterion for solving unconstrained optimization

Yiting Zhang; Chongyang He; Wanting Yuan; Mingyuan Cao; Yiting Zhang; Chongyang He; Wanting Yuan; Mingyuan Cao

doi:10.3934/math.20241528

AIMS Mathematics

2024, Volume 9, Issue 11: 31790-31805. doi: 10.3934/math.20241528

Previous Article Next Article

Research article

A novel nonmonotone trust region method based on the Metropolis criterion for solving unconstrained optimization

School of Mathematics and Statistics, Beihua University, Jilin 132013, China

Received: 13 September 2024 Revised: 17 October 2024 Accepted: 31 October 2024 Published: 08 November 2024
MSC : 49M37, 65K05, 90C30

In this paper, we propose a novel nonmonotone trust region method that incorporates the Metropolis criterion to construct a new function sequence. This sequence is used to update both the trust region ratio and the iteration criterion, increasing the likelihood of accepting the current trial step and introducing randomness into the iteration process. When the current trial step is not accepted, we introduce an improved nonmonotone line search technique to continue the iteration. This approach significantly reduces the number of subproblems that need to be solved, thereby saving computational resources. The stochastic nonmonotone technique helps the algorithm avoid being trapped in the local optima, and a global convergence is guaranteed under certain conditions. Numerical experiments demonstrate that the algorithm can be more effectively applied to a broader range of problems.
- optimization,
- trust region method,
- line search,
- metropolis criterion,
- nonmonotone
Citation: Yiting Zhang, Chongyang He, Wanting Yuan, Mingyuan Cao. A novel nonmonotone trust region method based on the Metropolis criterion for solving unconstrained optimization[J]. AIMS Mathematics, 2024, 9(11): 31790-31805. doi: 10.3934/math.20241528

Related Papers:

Abstract

In this paper, we propose a novel nonmonotone trust region method that incorporates the Metropolis criterion to construct a new function sequence. This sequence is used to update both the trust region ratio and the iteration criterion, increasing the likelihood of accepting the current trial step and introducing randomness into the iteration process. When the current trial step is not accepted, we introduce an improved nonmonotone line search technique to continue the iteration. This approach significantly reduces the number of subproblems that need to be solved, thereby saving computational resources. The stochastic nonmonotone technique helps the algorithm avoid being trapped in the local optima, and a global convergence is guaranteed under certain conditions. Numerical experiments demonstrate that the algorithm can be more effectively applied to a broader range of problems.

References

[1]	N. M. Alexandrov, J. E. Dennis, R. M. Lewis, V. Torczon, A trust region framework for managing the use of approximation models in optimization, Struct. Optim., 15 (1998), 16–23. https://doi.org/10.1007/BF01197433 doi: 10.1007/BF01197433
[2]	S. Babaie-Kafaki, R. Ghanbari, N. Mahdavi-Amiri, An efficient and practically robust hybrid metaheuristic algorithm for solving fuzzy bus terminal location problems, Asia-Pac. J. Oper. Res., 29 (2012), 1250009. https://doi.org/10.1142/S0217595912500091 doi: 10.1142/S0217595912500091
[3]	S. Babaie-Kafaki, S. Rezaee, A randomized nonmonotone adaptive trust region method based on the simulated annealing strategy for unconstrained optimization, Int. J. Intell. Comput., 12 (2019), 389–399. https://doi.org/10.1108/IJICC-12-2018-0178 doi: 10.1108/IJICC-12-2018-0178
[4]	J. Bai, L. Jia, Z. Peng, A new insight on augmented Lagrangian method with applications in machine learning, J. Sci. Comput., 99 (2024), 53. https://doi.org/10.1007/s10915-024-02518-0 doi: 10.1007/s10915-024-02518-0
[5]	J. Chen, W. Y. Sun, Nonmonotone adaptive trust-region algorithms with indefinite dogleg path for unconstrained minimization, Northeast. Math. J., 24 (2008), 19–30.
[6]	J. Deepho, A. B. Abubakar, M. Malik, I. K. Argyros, Solving unconstrained optimization problems via hybrid CD-DY conjugate gradient methods with applications, J. Comput. Appl. Math., 405 (2022), 113823. https://doi.org/10.1016/j.cam.2021.113823 doi: 10.1016/j.cam.2021.113823
[7]	N. Y. Deng, Y. Xiao, F. J. Zhou, Nonmonotonic trust region algorithm, J. Optim. Theory Appl., 76 (1993), 259–285. https://doi.org/10.1007/BF00939608 doi: 10.1007/BF00939608
[8]	S. Di, W. Sun, A trust region method for conic model to solve unconstraind optimizaions, Optim. Method. Softw., 6 (1996), 237–263. https://doi.org/10.1080/10556789608805637 doi: 10.1080/10556789608805637
[9]	E. D. Dolan, J. J. More, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201–213. https://doi.org/10.1007/s101070100263 doi: 10.1007/s101070100263
[10]	J. Fu, W. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Appl. Math. Comput., 163 (2005), 489–504. https://doi.org/10.1016/j.amc.2004.02.011 doi: 10.1016/j.amc.2004.02.011
[11]	E. M. Gertz, Combination trust-region line search methods for unconstrained optimization, San Diego: University of California, 1999.
[12]	L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23 (1986), 707–716. https://doi.org/10.1137/0723046 doi: 10.1137/0723046
[13]	N. Gu, J. Mo, Incorporating nonmonotone strategies into the trust region method for unconstrained optimization, Comput. Math. Appl., 55 (2008), 2158–2172. https://doi.org/10.1016/j.camwa.2007.08.038 doi: 10.1016/j.camwa.2007.08.038
[14]	M. Hatamian, M. Paripour, F. M. Yaghoobi, N. Karamikabir. An adaptive nonmonotone line search technique for solving systems of nonlinear equations, J. Math., 2021 (2021), 7134561. https://doi.org/10.1155/2021/7134561 doi: 10.1155/2021/7134561
[15]	D. Henderson, S. H. Jacobson, A. W. Johnson, The theory and practice of simulated annealing, In: Handbook of Metaheuristics, Boston: Springer, 2003, 287–319. https://doi.org/10.1007/0-306-48056-5_10
[16]	S. Huang, Z. Wan, J. Zhang, An extended nonmonotone line search technique for large-scale unconstrained optimization, J. Comput. Appl. Math., 330 (2018), 586–604. https://doi.org/10.1016/j.cam.2017.09.026 doi: 10.1016/j.cam.2017.09.026
[17]	S. Kirkpatrick, C. D. Gellat, M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671–680. https://doi.org/10.1126/science.220.4598.671 doi: 10.1126/science.220.4598.671
[18]	J. Lee, K. Jung, J. H. Kwon, The aerodynamic shape optimization of airfoils using unconstrained trust region methods, Eng. Optimiz., 41 (2009), 459–471. https://doi.org/10.1080/03052150802596068 doi: 10.1080/03052150802596068
[19]	T. Li, Z. Wan, J. Guo, A new nonmonotone spectral projected gradient algorithm for box-constrained optimization problems in m×n real matrix space with application in image clustering, J. Comput. Appl. Math., 438 (2024), 115563. https://doi.org/10.1016/j.cam.2023.115563 doi: 10.1016/j.cam.2023.115563
[20]	X. Li, W. Dong, Z. Peng, A new nonmonotone trust region Barzilai-Borwein method for unconstrained optimization problems, Acta Math. Appl. Sin. Engl. Ser., 37 (2021), 166–175. https://doi.org/10.1007/s10255-021-0997-9 doi: 10.1007/s10255-021-0997-9
[21]	Y. Liu, X. Liu, Application and performances of unconstrained optimization methods in seafloor AVO inversion, Arab. J. Geosci., 9 (2016), 652. https://doi.org/10.1007/s12517-016-2692-3 doi: 10.1007/s12517-016-2692-3
[22]	S. Lu, Z. Wei, L. Li, A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization, Comput. Optim. Appl., 51 (2012), 551–573. https://doi.org/10.1007/s10589-010-9363-1 doi: 10.1007/s10589-010-9363-1
[23]	Q. Ni, Optimality conditions for trust-region subproblems involving a conic model, SIAM J. Optim., 15 (2005), 826–837. https://doi.org/10.1137/S1052623402418991 doi: 10.1137/S1052623402418991
[24]	T. D. Niri, M. Heydari, M. M. Hosseini, Two nonmonotone trust region algorithms based on an improved Newton method, J. Appl. Math. Comput., 64 (2020), 179–194. https://doi.org/10.1007/s12190-020-01350-7 doi: 10.1007/s12190-020-01350-7
[25]	J. Nocedal, Y. Yuan, Combining trust region and line search techniques, Advances in nonlinear programming, Boston, MA: Springer, 1998, 153–175. https://doi.org/10.1007/978-1-4613-3335-7_7
[26]	S. Rezaee, S. Babaie-Kafaki, An adaptive nonmonotone trust region algorithm, Optim. method. softw., 34 (2019), 264–277. https://doi.org/10.1080/10556788.2017.1364738 doi: 10.1080/10556788.2017.1364738
[27]	S. Sun, J. Nocedal, A trust region method for noisy unconstrained optimization, Math. Program., 202 (2023), 445–472. https://doi.org/10.1007/s10107-023-01941-9 doi: 10.1007/s10107-023-01941-9
[28]	W. Sun, J. Han, J. Sun, Global convergence of nonmonotone descent methods for unconstrained optimization problems, J. Comput. Appl. Math., 146 (2002), 89–98. https://doi.org/10.1016/S0377-0427(02)00420-X doi: 10.1016/S0377-0427(02)00420-X
[29]	W. Sun, Nonmonotone trust region method for solving optimization problems, Appl. Math. Comput., 156 (2004), 159–174. https://doi.org/10.1016/j.amc.2003.07.008 doi: 10.1016/j.amc.2003.07.008
[30]	P. L. Toint, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Math. Program., 77 (1997), 69–94. https://doi.org/10.1007/BF02614518 doi: 10.1007/BF02614518
[31]	Z. Wan, Y. Chen, S. Huang, D. Feng, A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations, Optim. Lett., 8 (2014), 1845–1860. https://doi.org/10.1007/s11590-013-0678-6 doi: 10.1007/s11590-013-0678-6
[32]	X. S. Yang, Nature-inspired optimization algorithms, Academic Press, 2020. https://doi.org/10.1016/C2013-0-01368-0
[33]	G. L. Yuan, Z. X. Wei, A trust region algorithm with conjugate gradient technique for optimization problems, Numer. Func. Anal. Opt., 32 (2011), 212–232. https://doi.org/10.1080/01630563.2010.532273 doi: 10.1080/01630563.2010.532273
[34]	H. Zhang, W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004), 1043–1056. https://doi.org/10.1137/S1052623403428208 doi: 10.1137/S1052623403428208
[35]	Q. Y. Zhou, J. Chen, Z. W. Xie, A nonmonotone trust region method based on simple quadratic models, J. Comput. Appl. Math., 272 (2014), 107–115. https://doi.org/10.1016/j.cam.2014.04.026 doi: 10.1016/j.cam.2014.04.026

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)