American Institute of Mathematical Sciences

Advanced
  • 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

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

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-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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (56)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences