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 & 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. 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. 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. doi: 10.1007/BFb0121156.

[4]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust Region Methods,", SIAM, (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).

[6]

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

[7]

W. Davidon, Conic Approximations and Collinear Scalings for Optimizers,, SIAM Journal on Numerical Analysis, 17 (1980), 268. 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. 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. doi: 10.1080/10556789608805637.

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. 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, 2 (2012), 19. 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. 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. 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.

[19]

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

[20]

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

[21]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software,, ACM Transactions on Mathematical Software, 7 (1981), 17. 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. 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. 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. 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. doi: 10.1137/S1052623494266365.

[26]

S. B. Sheng, Interpolation by conic model for unconstrained optimization,, Computing, 54 (1995), 83. 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. 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. 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. doi: 10.1137/0720042.

[30]

W. Y. Sun, Nonmonotone trust region method for optimization,, Applied Mathematics and Computation, 156 (2004), 159. 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. doi: 10.1016/S0096-3003(98)10103-0.

[32]

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

[33]

H. P. Wu and Q. Ni, A new trust region algorithm with conic model,, Numerical Mathematics, 30 (2008), 57.

[34]

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

[35]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. 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. 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. 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. 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. doi: 10.1007/BFb0121156.

[4]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust Region Methods,", SIAM, (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).

[6]

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

[7]

W. Davidon, Conic Approximations and Collinear Scalings for Optimizers,, SIAM Journal on Numerical Analysis, 17 (1980), 268. 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. 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. doi: 10.1080/10556789608805637.

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. 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. 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. 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, 2 (2012), 19. 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. 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. 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.

[19]

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

[20]

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

[21]

J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software,, ACM Transactions on Mathematical Software, 7 (1981), 17. 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. 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. 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. 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. doi: 10.1137/S1052623494266365.

[26]

S. B. Sheng, Interpolation by conic model for unconstrained optimization,, Computing, 54 (1995), 83. 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. 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. 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. doi: 10.1137/0720042.

[30]

W. Y. Sun, Nonmonotone trust region method for optimization,, Applied Mathematics and Computation, 156 (2004), 159. 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. doi: 10.1016/S0096-3003(98)10103-0.

[32]

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

[33]

H. P. Wu and Q. Ni, A new trust region algorithm with conic model,, Numerical Mathematics, 30 (2008), 57.

[34]

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

[35]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. 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. doi: 10.1137/S1052623403428208.

[1]

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

[2]

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

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

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

[5]

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

[6]

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

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

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

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

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

[11]

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 & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070

[12]

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

[13]

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 & Management Optimization, 2017, 13 (5) : 1-23. doi: 10.3934/jimo.2018117

[14]

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

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

Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595

[17]

Bum Il Hong, Nahmwoo Hahm, Sun-Ho Choi. SIR Rumor spreading model with trust rate distribution. Networks & Heterogeneous Media, 2018, 13 (3) : 515-530. doi: 10.3934/nhm.2018023

[18]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395

[19]

Chunlei Zhang, Qin Sheng, Raúl Ordóñez. Notes on the convergence and applications of surrogate optimization. Conference Publications, 2005, 2005 (Special) : 947-956. doi: 10.3934/proc.2005.2005.947

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]