• 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 and 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.

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

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

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

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

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

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

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

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

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

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

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

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

[14]

J. Nocedal and S. J. Wright, "Numerical Optimization,'' $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.

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

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

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

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

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

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

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

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

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

[24]

Y. X. Yuan, On the convergence of trust region algorithms, (in Chinese) Mathematica Numerica Sinica, 16 (1994), 333-346.

[25]

Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'' (in Chinese) Science Press, Beijing, 1997.

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

[27]

D. T. Zhu, A nonmonotone trust region technique for unconstrained optimization problems, Systems Science and Mathematical Sciences, 11 (1998), 375-382.

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.

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

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

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

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

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

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

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

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

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

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

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

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

[14]

J. Nocedal and S. J. Wright, "Numerical Optimization,'' $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.

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

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

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

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

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

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

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

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

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

[24]

Y. X. Yuan, On the convergence of trust region algorithms, (in Chinese) Mathematica Numerica Sinica, 16 (1994), 333-346.

[25]

Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'' (in Chinese) Science Press, Beijing, 1997.

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

[27]

D. T. Zhu, A nonmonotone trust region technique for unconstrained optimization problems, Systems Science and Mathematical Sciences, 11 (1998), 375-382.

[1]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[8]

Jirui Ma, Jinyan Fan. On convergence properties of the modified trust region method under Hölderian error bound condition. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021222

[9]

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 and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[10]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[11]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[12]

Sergiu Aizicovici, Simeon Reich. Anti-periodic solutions to a class of non-monotone evolution equations. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 35-42. doi: 10.3934/dcds.1999.5.35

[13]

Alfonso Castro, Benjamin Preskill. Existence of solutions for a semilinear wave equation with non-monotone nonlinearity. Discrete and Continuous Dynamical Systems, 2010, 28 (2) : 649-658. doi: 10.3934/dcds.2010.28.649

[14]

José Caicedo, Alfonso Castro, Arturo Sanjuán. Bifurcation at infinity for a semilinear wave equation with non-monotone nonlinearity. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1857-1865. doi: 10.3934/dcds.2017078

[15]

Arturo Hidalgo, Lourdes Tello. On a global climate model with non-monotone multivalued coalbedo. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022093

[16]

Yuxiang Zhang, Shiwang Ma. Invasion dynamics of a diffusive pioneer-climax model: Monotone and non-monotone cases. Discrete and Continuous Dynamical Systems - B, 2021, 26 (9) : 4767-4788. doi: 10.3934/dcdsb.2020312

[17]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[18]

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 and Continuous Dynamical Systems - S, 2017, 10 (3) : 581-603. doi: 10.3934/dcdss.2017029

[19]

Abraham Solar. Stability of non-monotone and backward waves for delay non-local reaction-diffusion equations. Discrete and Continuous Dynamical Systems, 2019, 39 (10) : 5799-5823. doi: 10.3934/dcds.2019255

[20]

Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 317-330. doi: 10.3934/naco.2020004

2020 Impact Factor: 1.801

Metrics

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

Other articles
by authors

[Back to Top]