• 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

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.

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

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

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

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

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

[7]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. doi: 10.1016/j.cam.2006.10.070.

[12]

J. J. Moré, Recent developments in algorithms and software for trust region methods,, in, (1983), 258.

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

[14]

J. Nocedal and S. J. Wright, "Numerical Optimization,'', $2^{nd}$ edition, (2006).

[15]

M. J. D. Powell, A hybrid method for nonlinear equations,, in, (1970), 87.

[16]

M. J. D. Powell, Convergence properties of a class of minimization algorithms,, in, (1974), 1.

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

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

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

[20]

W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods. Nonlinear Programming,'', Springer Optimization and Its Applications, (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. 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. 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. doi: 10.1007/BF02614518.

[24]

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

[25]

Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'', (in Chinese) Science Press, (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. 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.

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.

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

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

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

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

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

[7]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. doi: 10.1016/j.cam.2006.10.070.

[12]

J. J. Moré, Recent developments in algorithms and software for trust region methods,, in, (1983), 258.

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

[14]

J. Nocedal and S. J. Wright, "Numerical Optimization,'', $2^{nd}$ edition, (2006).

[15]

M. J. D. Powell, A hybrid method for nonlinear equations,, in, (1970), 87.

[16]

M. J. D. Powell, Convergence properties of a class of minimization algorithms,, in, (1974), 1.

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

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

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

[20]

W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods. Nonlinear Programming,'', Springer Optimization and Its Applications, (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. 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. 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. doi: 10.1007/BF02614518.

[24]

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

[25]

Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'', (in Chinese) Science Press, (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. 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.

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

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]