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

Previous Article
Equilibrium joining probabilities in observable queues with general service and setup times
JIMO Home
This Issue
Next Article
Integrated imperfect production inventory model under permissible delay in payments depending on the order quantity

October 2013, 9(4): 919-944. doi: 10.3934/jimo.2013.9.919

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

Jun Chen ^1, , Wenyu Sun ^1, and Zhenghao Yang ^2,

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

Abstract
Related Papers

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.

Keywords: convergence analysis, CUTEr., retrospective trust-region method, Unconstrained optimization, non-monotone technique.

Mathematics Subject Classification: 90C30, 90C26, 65K0.

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. 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. 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. 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. 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, (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. doi: 10.1007/BF00939608. Google Scholar
[7]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. 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, (1983), 258. 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. doi: 10.1137/0904038. Google Scholar
[14]	J. Nocedal and S. J. Wright, "Numerical Optimization,'', $2^{nd}$ edition, (2006). Google Scholar
[15]	M. J. D. Powell, A hybrid method for nonlinear equations,, in, (1970), 87. Google Scholar
[16]	M. J. D. Powell, Convergence properties of a class of minimization algorithms,, in, (1974), 1. 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. 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. 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. 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, (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. 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. 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. 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. Google Scholar
[25]	Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'', (in Chinese) Science Press, (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. 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. 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. 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. 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. 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. 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, (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. doi: 10.1007/BF00939608. Google Scholar
[7]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. 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, (1983), 258. 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. doi: 10.1137/0904038. Google Scholar
[14]	J. Nocedal and S. J. Wright, "Numerical Optimization,'', $2^{nd}$ edition, (2006). Google Scholar
[15]	M. J. D. Powell, A hybrid method for nonlinear equations,, in, (1970), 87. Google Scholar
[16]	M. J. D. Powell, Convergence properties of a class of minimization algorithms,, in, (1974), 1. 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. 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. 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. 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, (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. 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. 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. 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. Google Scholar
[25]	Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'', (in Chinese) Science Press, (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. 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. 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]	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
[8]	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
[9]	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
[10]	Sergiu Aizicovici, Simeon Reich. Anti-periodic solutions to a class of non-monotone evolution equations. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 35-42. doi: 10.3934/dcds.1999.5.35
[11]	Alfonso Castro, Benjamin Preskill. Existence of solutions for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 649-658. doi: 10.3934/dcds.2010.28.649
[12]	José Caicedo, Alfonso Castro, Arturo Sanjuán. Bifurcation at infinity for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1857-1865. doi: 10.3934/dcds.2017078
[13]	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
[14]	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
[15]	Abraham Solar. Stability of non-monotone and backward waves for delay non-local reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 5799-5823. doi: 10.3934/dcds.2019255
[16]	Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239
[17]	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 - A, 2016, 36 (3) : 1331-1353. doi: 10.3934/dcds.2016.36.1331
[18]	Pablo Amster, Manuel Zamora. Periodic solutions for indefinite singular equations with singularities in the spatial variable and non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4819-4835. doi: 10.3934/dcds.2018211
[19]	Anatoli F. Ivanov, Bernhard Lani-Wayda. Periodic solutions for three-dimensional non-monotone cyclic systems with time delays. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 667-692. doi: 10.3934/dcds.2004.11.667
[20]	José Caicedo, Alfonso Castro, Rodrigo Duque, Arturo Sanjuán. Existence of $L^p$-solutions for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - S, 2014, 7 (6) : 1193-1202. doi: 10.3934/dcdss.2014.7.1193

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences