2013, 3(2): 309-325. doi: 10.3934/naco.2013.3.309

Nonmonotone retrospective conic trust region method for unconstrained optimization

1. 

School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China

2. 

School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046

Received  June 2012 Revised  January 2013 Published  April 2013

We propose a retrospective conic trust region method for unconstrained optimization. It can be regarded as an extension of the retrospective trust region method based on a quadratic model which was first proposed by Bastin et al (2010). Nonmonotone technique is added to accelerate the speed of the algorithm. Under some mild conditions, the sequence generated by our algorithm converges to a stationary point. Numerical tests on a set of standard testing problems confirm the efficiency of our new method.
Citation: 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
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]

J. F. Bonnans, E. R. Panier, A. L. Tits and J. L. Zhou, Avoiding the maratos effect by means of a nonmonotone line search II. inequalities constrained problems - feasibility iterates, SIAM Journal on Numerical Analysis, 29 (1992), 1187-1202. doi: 10.1137/0729072.

[3]

J. P. Bulteau and J. P. Vial, Curvilinear path and trust region in unconstrained optimization: a convergence analysis, Mathematical Programming Study, 30 (1987), 82-101. doi: 10.1007/BFb0121156.

[4]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust Region Methods," SIAM, Philadelphia, USA, 2000. doi: 10.1137/1.9780898719857.

[5]

J. Chen, W. Y. Sun and Z. H. Yang, A nonmonotone retrospective trust region method for unconstrained optimization, Journal of Industrial and Management Optimization, (2013), to appear.

[6]

Y. H. Dai, On the nonmonotone line search, Journal of Optimization Theory and Applications, 112 (2002), 315-330. doi: 10.1023/A:1013653923062.

[7]

W. Davidon, Conic Approximations and Collinear Scalings for Optimizers, SIAM Journal on Numerical Analysis, 17 (1980), 268-281. doi: 10.1137/0717023.

[8]

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.

[9]

S. Di and W. Y. Sun, A trust region method for conic model to solve unconstraind optimizations, Optimization Methods and Software, 6 (1996), 237-263. doi: 10.1080/10556789608805637.

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.

[11]

M. C. Ferris, S. Lucidi and M. Roma, Nonmonotone curvilinear line search methods for unconstrained optimization, Computational Optimization and Applications, 6 (1996), 117-136. doi: 10.1007/BF00249642.

[12]

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.

[13]

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.

[14]

L. Grippo, F. Lampariello and S. Lucidi, A truncated Newton method with nonmonotone line search for unconstrained optimization, Journal of Optimization Theory and Applications, 60 (1989), 401-419. doi: 10.1007/BF00940345.

[15]

C. L. Hao and X. W. Liu, Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints, Numerical Algebra, Control and Optimization, 2 (2012), 19-29. doi: 10.3934/naco.2012.2.19.

[16]

Y. Ji, Y. J. Li, K. C. Zhang and X. L. Zhang, A new nonmonotone trust-region method of conic model for solving unconstrained optimization, Journal of Computational and Applied Mathematics, 233 (2010), 1746-1754. doi: 10.1016/j.cam.2009.09.011.

[17]

Y. Lu and Z. W. Chen, A retrospective filter trust region algorithm for unconstrained optimization, Applied Mathematics, 1 (2010), 179-188. doi: 10.4236/am.2010.13022.

[18]

X. P. Lu and Q. Ni, A dogleg method for solving new trust region subproblems of conic model, Acta Mathematicae Applicatae Sinica, 30 (1997), 1-17.

[19]

X. J. Miao and Z. H. Liu, An adaptive retrospective trust region method for unconstrained optimization, IEEE Conference, (2010), 957-960.

[20]

J. J. Moré, Recent development in algorithms and software for trust region methods, Mathematical Programming: the State of the Art, Springer, Berlin, (1983), 258-287.

[21]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 7 (1981), 17-41. doi: 10.1145/355934.355936.

[22]

Q. Ni, Optimality conditions for trust region subproblems involving a conic model, SIAM Journal on Optimization, 15 (2005), 828-837. doi: 10.1137/S1052623402418991.

[23]

M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained minimization, Mathematical Programming, 29 (1984), 297-303. doi: 10.1007/BF02591998.

[24]

S. J. Qu and S. D. Jiang, A trust region method with a conic model for unconstrained optimization, Mathematical Methods In The Applied Sciences, 31 (2008), 1780-1808. doi: 10.1002/mma.997.

[25]

M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problems, SIAM Jounal on Optimization, 7 (1997), 26-33. doi: 10.1137/S1052623494266365.

[26]

S. B. Sheng, Interpolation by conic model for unconstrained optimization, Computing, 54 (1995), 83-98. doi: 10.1007/BF02238081.

[27]

G. A. Shultz, R. B. Schnabel and R. H. Byrid, 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.

[28]

D. C. Sorensen, The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization, SIAM Jounal on Numerical Analysis, 17 (1980), 84-114. doi: 10.1137/0717011.

[29]

T. Steihaug, The conjugate gradient method and trust region in large scale optimization, SIAM Journal on Numerical Analysis, 20 (1983), 626-637. doi: 10.1137/0720042.

[30]

W. Y. Sun, Nonmonotone trust region method for optimization, Applied Mathematics and Computation, 156 (2004), 159-174. doi: 10.1016/j.amc.2003.07.008.

[31]

W. Y. Sun, R. J. B. Sampaio and J. Y. Yuan, Quasi-Newton trust region algorithm for non-smooth least squares problems, Applied Mathematics and Computation, 105 (1999), 183-194. doi: 10.1016/S0096-3003(98)10103-0.

[32]

W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer, New York, 2006.

[33]

H. P. Wu and Q. Ni, A new trust region algorithm with conic model, Numerical Mathematics, A Journal of Chinese Universities, 30 (2008), 57-63.

[34]

H. Yamashita, A globally convergent primal dual interior point method for constrained optimization, Optimization Methods and Software, 10 (1998), 443-469. doi: 10.1080/10556789808805723.

[35]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34. doi: 10.3934/naco.2011.1.15.

[36]

H. C. Zhang and W. W. Hager, A nonmontone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056. doi: 10.1137/S1052623403428208.

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]

J. F. Bonnans, E. R. Panier, A. L. Tits and J. L. Zhou, Avoiding the maratos effect by means of a nonmonotone line search II. inequalities constrained problems - feasibility iterates, SIAM Journal on Numerical Analysis, 29 (1992), 1187-1202. doi: 10.1137/0729072.

[3]

J. P. Bulteau and J. P. Vial, Curvilinear path and trust region in unconstrained optimization: a convergence analysis, Mathematical Programming Study, 30 (1987), 82-101. doi: 10.1007/BFb0121156.

[4]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust Region Methods," SIAM, Philadelphia, USA, 2000. doi: 10.1137/1.9780898719857.

[5]

J. Chen, W. Y. Sun and Z. H. Yang, A nonmonotone retrospective trust region method for unconstrained optimization, Journal of Industrial and Management Optimization, (2013), to appear.

[6]

Y. H. Dai, On the nonmonotone line search, Journal of Optimization Theory and Applications, 112 (2002), 315-330. doi: 10.1023/A:1013653923062.

[7]

W. Davidon, Conic Approximations and Collinear Scalings for Optimizers, SIAM Journal on Numerical Analysis, 17 (1980), 268-281. doi: 10.1137/0717023.

[8]

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.

[9]

S. Di and W. Y. Sun, A trust region method for conic model to solve unconstraind optimizations, Optimization Methods and Software, 6 (1996), 237-263. doi: 10.1080/10556789608805637.

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.

[11]

M. C. Ferris, S. Lucidi and M. Roma, Nonmonotone curvilinear line search methods for unconstrained optimization, Computational Optimization and Applications, 6 (1996), 117-136. doi: 10.1007/BF00249642.

[12]

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.

[13]

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.

[14]

L. Grippo, F. Lampariello and S. Lucidi, A truncated Newton method with nonmonotone line search for unconstrained optimization, Journal of Optimization Theory and Applications, 60 (1989), 401-419. doi: 10.1007/BF00940345.

[15]

C. L. Hao and X. W. Liu, Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints, Numerical Algebra, Control and Optimization, 2 (2012), 19-29. doi: 10.3934/naco.2012.2.19.

[16]

Y. Ji, Y. J. Li, K. C. Zhang and X. L. Zhang, A new nonmonotone trust-region method of conic model for solving unconstrained optimization, Journal of Computational and Applied Mathematics, 233 (2010), 1746-1754. doi: 10.1016/j.cam.2009.09.011.

[17]

Y. Lu and Z. W. Chen, A retrospective filter trust region algorithm for unconstrained optimization, Applied Mathematics, 1 (2010), 179-188. doi: 10.4236/am.2010.13022.

[18]

X. P. Lu and Q. Ni, A dogleg method for solving new trust region subproblems of conic model, Acta Mathematicae Applicatae Sinica, 30 (1997), 1-17.

[19]

X. J. Miao and Z. H. Liu, An adaptive retrospective trust region method for unconstrained optimization, IEEE Conference, (2010), 957-960.

[20]

J. J. Moré, Recent development in algorithms and software for trust region methods, Mathematical Programming: the State of the Art, Springer, Berlin, (1983), 258-287.

[21]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 7 (1981), 17-41. doi: 10.1145/355934.355936.

[22]

Q. Ni, Optimality conditions for trust region subproblems involving a conic model, SIAM Journal on Optimization, 15 (2005), 828-837. doi: 10.1137/S1052623402418991.

[23]

M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained minimization, Mathematical Programming, 29 (1984), 297-303. doi: 10.1007/BF02591998.

[24]

S. J. Qu and S. D. Jiang, A trust region method with a conic model for unconstrained optimization, Mathematical Methods In The Applied Sciences, 31 (2008), 1780-1808. doi: 10.1002/mma.997.

[25]

M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problems, SIAM Jounal on Optimization, 7 (1997), 26-33. doi: 10.1137/S1052623494266365.

[26]

S. B. Sheng, Interpolation by conic model for unconstrained optimization, Computing, 54 (1995), 83-98. doi: 10.1007/BF02238081.

[27]

G. A. Shultz, R. B. Schnabel and R. H. Byrid, 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.

[28]

D. C. Sorensen, The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization, SIAM Jounal on Numerical Analysis, 17 (1980), 84-114. doi: 10.1137/0717011.

[29]

T. Steihaug, The conjugate gradient method and trust region in large scale optimization, SIAM Journal on Numerical Analysis, 20 (1983), 626-637. doi: 10.1137/0720042.

[30]

W. Y. Sun, Nonmonotone trust region method for optimization, Applied Mathematics and Computation, 156 (2004), 159-174. doi: 10.1016/j.amc.2003.07.008.

[31]

W. Y. Sun, R. J. B. Sampaio and J. Y. Yuan, Quasi-Newton trust region algorithm for non-smooth least squares problems, Applied Mathematics and Computation, 105 (1999), 183-194. doi: 10.1016/S0096-3003(98)10103-0.

[32]

W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer, New York, 2006.

[33]

H. P. Wu and Q. Ni, A new trust region algorithm with conic model, Numerical Mathematics, A Journal of Chinese Universities, 30 (2008), 57-63.

[34]

H. Yamashita, A globally convergent primal dual interior point method for constrained optimization, Optimization Methods and Software, 10 (1998), 443-469. doi: 10.1080/10556789808805723.

[35]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34. doi: 10.3934/naco.2011.1.15.

[36]

H. C. Zhang and W. W. Hager, A nonmontone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056. doi: 10.1137/S1052623403428208.

[1]

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

[2]

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

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

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

[5]

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

[6]

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

[7]

Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021143

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

Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046

[11]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial and Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411

[12]

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

[13]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032

[14]

Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117

[15]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070

[16]

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

[17]

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

[18]

Chufen Wu, Dongmei Xiao, Xiao-Qiang Zhao. Asymptotic pattern of a migratory and nonmonotone population model. Discrete and Continuous Dynamical Systems - B, 2014, 19 (4) : 1171-1195. doi: 10.3934/dcdsb.2014.19.1171

[19]

Lixing Han. An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 583-599. doi: 10.3934/naco.2013.3.583

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]