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

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

[2]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[3]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[4]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[5]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[6]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

[7]

Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104

[8]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[9]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[10]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[11]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[12]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[13]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024

[14]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[15]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[16]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[17]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[18]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[19]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[20]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]