# American Institute of Mathematical Sciences

• Previous Article
Integrated imperfect production inventory model under permissible delay in payments depending on the order quantity
• JIMO Home
• This Issue
• Next Article
Equilibrium joining probabilities in observable queues with general service and setup times
October  2013, 9(4): 919-944. doi: 10.3934/jimo.2013.9.919

## A non-monotone retrospective trust-region method for unconstrained optimization

 1 School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046, China 2 Department of Applied Mathematics, Nanjing Agricultural University, Nanjing 210095, China

Received  January 2012 Revised  April 2013 Published  August 2013

In this paper, a new non-monotone trust-region algorithm is proposed for solving unconstrained nonlinear optimization problems. We modify the retrospective ratio which is introduced by Bastin et al. [Math. Program., Ser. A (2010) 123: 395-418] to form a convex combination ratio for updating the trust-region radius. Then we combine the non-monotone technique with this new framework of trust-region algorithm. The new algorithm is shown to be globally convergent to a first-order critical point. Numerical experiments on CUTEr problems indicate that it is competitive with both the original retrospective trust-region algorithm and the classical trust-region algorithms.
Citation: Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
##### References:
 [1] F. Bastin, V. Malmedy, M. Mouffe, Ph. L. Toint and D. Tomanos, A retrospective trust-region method for unconstrained optimization, Mathematical Programming, 123 (2010), 395-418. doi: 10.1007/s10107-008-0258-1.  Google Scholar [2] I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Transactions on Mathematical Software, 21 (1995), 123-160. doi: 10.1145/200979.201043.  Google Scholar [3] R. M. Chamberlain, M. J. D. Powell, C. Lemaréchal and H. C. Pedersen, The watchdog technique for forcing convergence in algorithms for constrained optimization, Mathematical Programming Studies, 16 (1982), 1-17.  Google Scholar [4] J. Chen, W. Y. Sun and R. J. B. de Sampaio, Numerical research on the sensitivity of nonmonotone trust region algorithms to their parameters, Computers and Mathematics with Applications, 56 (2008), 2932-2940. doi: 10.1016/j.camwa.2008.05.010.  Google Scholar [5] A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,'' MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.  Google Scholar [6] N. Y. Deng, Y. Xiao and F. J. Zhou, Nonmonotonic trust region algorithm, Journal of Optimization Theory and Applications, 76 (1993), 259-285. doi: 10.1007/BF00939608.  Google Scholar [7] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, Series A, 91 (2002), 201-213. doi: 10.1007/s101070100263.  Google Scholar [8] J. H. Fu and W. Y. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Applied Mathematics and Computation, 163 (2005), 489-504. doi: 10.1016/j.amc.2004.02.011.  Google Scholar [9] N. I. M. Gould, D. Orban and Ph. L. Toint, CUTEr and SifDec: A Constrained and Unconstrained Testing Environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 373-394. doi: 10.1145/962437.962438.  Google Scholar [10] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for newton's method, SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar [11] J. T. Mo, C. Y. Liu and S. C. Yan, A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values, Journal of Computational and Applied Mathematics, 209 (2007), 97-108. doi: 10.1016/j.cam.2006.10.070.  Google Scholar [12] J. J. Moré, Recent developments in algorithms and software for trust region methods, in "Mathematical Programming: The State of the Art" (eds. A. Bachem, M. Grötschel and B. Korte), Springer, Berlin, (1983), 258-287.  Google Scholar [13] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572. doi: 10.1137/0904038.  Google Scholar [14] J. Nocedal and S. J. Wright, "Numerical Optimization,'' $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.  Google Scholar [15] M. J. D. Powell, A hybrid method for nonlinear equations, in "Numerical Methods for Nonlinear Algebraic Equations" (ed. P. Rabinowitz), Gordon and Breach, London, (1970), 87-114.  Google Scholar [16] M. J. D. Powell, Convergence properties of a class of minimization algorithms, in "Nonlinear Programming, 2" (eds. O. L. Mangasarian, R. R. Meyer and S. M. Robinson), Academic Press, London, (1974), 1-27.  Google Scholar [17] G. A. Shultz, R. B. Schnabel and R. H. Byrd, A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties, SIAM Journal on Numerical Analysis, 22 (1985), 47-67. doi: 10.1137/0722003.  Google Scholar [18] W. Y. Sun, Nonmonotone trust region method for solving optimization problems, Applied Mathematics and Computation, 156 (2004), 159-174. doi: 10.1016/j.amc.2003.07.008.  Google Scholar [19] W. Y. Sun, J. Y. Han and J. Sun, Global convergence of nonmonotone descent methods for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 146 (2002), 89-98. doi: 10.1016/S0377-0427(02)00420-X.  Google Scholar [20] W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods. Nonlinear Programming,'' Springer Optimization and Its Applications, Vol. 1, Springer, New York, 2006.  Google Scholar [21] W. Y. Sun and Q. Y. Zhou, An unconstrained optimization method using nonmonotone second order Goldstein's line search, Science in China Series A: Mathematics, 50 (2007), 1389-1400. doi: 10.1007/s11425-007-0072-x.  Google Scholar [22] Ph. L. Toint, An assessment of nonmonotone linesearch techniques for unconstrained optimization, SIAM Journal on Scientific Computing, 17 (1996), 725-739. doi: 10.1137/S106482759427021X.  Google Scholar [23] Ph. L. Toint, A non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Mathematical Programming, 77 (1997), 69-94. doi: 10.1007/BF02614518.  Google Scholar [24] Y. X. Yuan, On the convergence of trust region algorithms, (in Chinese) Mathematica Numerica Sinica, 16 (1994), 333-346.  Google Scholar [25] Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'' (in Chinese) Science Press, Beijing, 1997. Google Scholar [26] H. C. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056. doi: 10.1137/S1052623403428208.  Google Scholar [27] D. T. Zhu, A nonmonotone trust region technique for unconstrained optimization problems, Systems Science and Mathematical Sciences, 11 (1998), 375-382.  Google Scholar

show all references

##### References:
 [1] F. Bastin, V. Malmedy, M. Mouffe, Ph. L. Toint and D. Tomanos, A retrospective trust-region method for unconstrained optimization, Mathematical Programming, 123 (2010), 395-418. doi: 10.1007/s10107-008-0258-1.  Google Scholar [2] I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Transactions on Mathematical Software, 21 (1995), 123-160. doi: 10.1145/200979.201043.  Google Scholar [3] R. M. Chamberlain, M. J. D. Powell, C. Lemaréchal and H. C. Pedersen, The watchdog technique for forcing convergence in algorithms for constrained optimization, Mathematical Programming Studies, 16 (1982), 1-17.  Google Scholar [4] J. Chen, W. Y. Sun and R. J. B. de Sampaio, Numerical research on the sensitivity of nonmonotone trust region algorithms to their parameters, Computers and Mathematics with Applications, 56 (2008), 2932-2940. doi: 10.1016/j.camwa.2008.05.010.  Google Scholar [5] A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,'' MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.  Google Scholar [6] N. Y. Deng, Y. Xiao and F. J. Zhou, Nonmonotonic trust region algorithm, Journal of Optimization Theory and Applications, 76 (1993), 259-285. doi: 10.1007/BF00939608.  Google Scholar [7] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, Series A, 91 (2002), 201-213. doi: 10.1007/s101070100263.  Google Scholar [8] J. H. Fu and W. Y. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Applied Mathematics and Computation, 163 (2005), 489-504. doi: 10.1016/j.amc.2004.02.011.  Google Scholar [9] N. I. M. Gould, D. Orban and Ph. L. Toint, CUTEr and SifDec: A Constrained and Unconstrained Testing Environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 373-394. doi: 10.1145/962437.962438.  Google Scholar [10] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for newton's method, SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar [11] J. T. Mo, C. Y. Liu and S. C. Yan, A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values, Journal of Computational and Applied Mathematics, 209 (2007), 97-108. doi: 10.1016/j.cam.2006.10.070.  Google Scholar [12] J. J. Moré, Recent developments in algorithms and software for trust region methods, in "Mathematical Programming: The State of the Art" (eds. A. Bachem, M. Grötschel and B. Korte), Springer, Berlin, (1983), 258-287.  Google Scholar [13] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572. doi: 10.1137/0904038.  Google Scholar [14] J. Nocedal and S. J. Wright, "Numerical Optimization,'' $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.  Google Scholar [15] M. J. D. Powell, A hybrid method for nonlinear equations, in "Numerical Methods for Nonlinear Algebraic Equations" (ed. P. Rabinowitz), Gordon and Breach, London, (1970), 87-114.  Google Scholar [16] M. J. D. Powell, Convergence properties of a class of minimization algorithms, in "Nonlinear Programming, 2" (eds. O. L. Mangasarian, R. R. Meyer and S. M. Robinson), Academic Press, London, (1974), 1-27.  Google Scholar [17] G. A. Shultz, R. B. Schnabel and R. H. Byrd, A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties, SIAM Journal on Numerical Analysis, 22 (1985), 47-67. doi: 10.1137/0722003.  Google Scholar [18] W. Y. Sun, Nonmonotone trust region method for solving optimization problems, Applied Mathematics and Computation, 156 (2004), 159-174. doi: 10.1016/j.amc.2003.07.008.  Google Scholar [19] W. Y. Sun, J. Y. Han and J. Sun, Global convergence of nonmonotone descent methods for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 146 (2002), 89-98. doi: 10.1016/S0377-0427(02)00420-X.  Google Scholar [20] W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods. Nonlinear Programming,'' Springer Optimization and Its Applications, Vol. 1, Springer, New York, 2006.  Google Scholar [21] W. Y. Sun and Q. Y. Zhou, An unconstrained optimization method using nonmonotone second order Goldstein's line search, Science in China Series A: Mathematics, 50 (2007), 1389-1400. doi: 10.1007/s11425-007-0072-x.  Google Scholar [22] Ph. L. Toint, An assessment of nonmonotone linesearch techniques for unconstrained optimization, SIAM Journal on Scientific Computing, 17 (1996), 725-739. doi: 10.1137/S106482759427021X.  Google Scholar [23] Ph. L. Toint, A non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Mathematical Programming, 77 (1997), 69-94. doi: 10.1007/BF02614518.  Google Scholar [24] Y. X. Yuan, On the convergence of trust region algorithms, (in Chinese) Mathematica Numerica Sinica, 16 (1994), 333-346.  Google Scholar [25] Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'' (in Chinese) Science Press, Beijing, 1997. Google Scholar [26] H. C. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056. doi: 10.1137/S1052623403428208.  Google Scholar [27] D. T. Zhu, A nonmonotone trust region technique for unconstrained optimization problems, Systems Science and Mathematical Sciences, 11 (1998), 375-382.  Google Scholar
 [1] Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309 [2] Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223 [3] Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117 [4] Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321 [5] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [6] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 [7] Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 [8] Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 [9] Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 [10] Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 [11] Sergiu Aizicovici, Simeon Reich. Anti-periodic solutions to a class of non-monotone evolution equations. Discrete & Continuous Dynamical Systems, 1999, 5 (1) : 35-42. doi: 10.3934/dcds.1999.5.35 [12] Alfonso Castro, Benjamin Preskill. Existence of solutions for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems, 2010, 28 (2) : 649-658. doi: 10.3934/dcds.2010.28.649 [13] José Caicedo, Alfonso Castro, Arturo Sanjuán. Bifurcation at infinity for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems, 2017, 37 (4) : 1857-1865. doi: 10.3934/dcds.2017078 [14] Yuxiang Zhang, Shiwang Ma. Invasion dynamics of a diffusive pioneer-climax model: Monotone and non-monotone cases. Discrete & Continuous Dynamical Systems - B, 2021, 26 (9) : 4767-4788. doi: 10.3934/dcdsb.2020312 [15] Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034 [16] Zhao-Xing Yang, Guo-Bao Zhang, Ge Tian, Zhaosheng Feng. Stability of non-monotone non-critical traveling waves in discrete reaction-diffusion equations with time delay. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 581-603. doi: 10.3934/dcdss.2017029 [17] Abraham Solar. Stability of non-monotone and backward waves for delay non-local reaction-diffusion equations. Discrete & Continuous Dynamical Systems, 2019, 39 (10) : 5799-5823. doi: 10.3934/dcds.2019255 [18] Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 317-330. doi: 10.3934/naco.2020004 [19] Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239 [20] Rui Huang, Ming Mei, Kaijun Zhang, Qifeng Zhang. Asymptotic stability of non-monotone traveling waves for time-delayed nonlocal dispersion equations. Discrete & Continuous Dynamical Systems, 2016, 36 (3) : 1331-1353. doi: 10.3934/dcds.2016.36.1331

2019 Impact Factor: 1.366