• Original Articles • Previous Articles     Next Articles

A RETROSPECTIVE TRUST REGION ALGORITHM WITH TRUST REGION CONVERGING TO ZERO

Jinyan Fan1, Jianyu Pan2, Hongyan Song3   

  1. 1. School of Mathematical Sciences, and MOE-LSC, Shanghai Jiao Tong University, Shanghai 200240, China;
    2. Department of Mathematics, Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, China;
    3. School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2015-09-21 Revised:2015-12-14 Online:2016-07-15 Published:2016-07-15

Jinyan Fan, Jianyu Pan, Hongyan Song. A RETROSPECTIVE TRUST REGION ALGORITHM WITH TRUST REGION CONVERGING TO ZERO[J]. Journal of Computational Mathematics, 2016, 34(4): 421-436.

We propose a retrospective trust region algorithm with the trust region converging to zero for the unconstrained optimization problem. Unlike traditional trust region algorithms, the algorithm updates the trust region radius according to the retrospective ratio, which uses the most recent model information. We show that the algorithm preserves the global convergence of traditional trust region algorithms. The superlinear convergence is also proved under some suitable conditions.

CLC Number: 

[1] F. Bastin, V. Malmedy, M. Mouffe, Ph. L. Toint and D. Tomanos, A retrospective trust-region method for unconstrained optimization, Math. Program., Ser. A, 123(2010), 395-418.

[2] A.R. Conn, N.I.M. Gould and Ph.L. Toint, Trust-Region Methods, Number 01 in "MPS-SIAM Series on Optimization."SIAM, Philadelphia, 2000.

[3] J.E. Dennis and J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28(1974), 549-560.

[4] E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91(2002), 201-213.

[5] J.Y. Fan and Y.X. Yuan, A new trust region algorithm with trust region radius converging to zero, in Proceedings of the 5th International Conference on Optimization:Techniques and Applications, D. Li et al. (eds.), Hongkong, Dec. 2001, 786-794.

[6] D.M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comp., 2(1981), 186-197.

[7] N.I.M. Gould, D. Orban and Ph. L. Toint, CUTEr, a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 29(2003), 373-394.

[8] J.J. Moré, Recent developments in algorithms and software for trust region methods, In Mathe-matical Programming:The State of Art, A. Bachem, M. Grötschel and B. Korte (eds.), Springer, Berlin, 1983, 258-287.

[9] J.J. Moré, B.S. Garbow and K.H. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software, 7(1981), 17-41.

[10] J.J. Moré and D.C. Sorensen, Computing a trust region step SIAM J. Sci. Stat. Comp., 4(1983), 553-572.

[11] J. Nocedal and Y.X. Yuan, Combining trust region and line search techniques, in Advances in Nonlinear Programming, Y. Yuan (ed.), Kluwer, 1998, 153-175.

[12] M.J.D. Powell, A new algorithm for unconstrained optimization, in Nonlinear Programming, J. B. Rosen, O. L. Mangasarian and K. Ritter (eds.), Academic Press, New York, 1970, 31-66.

[13] M.J.D. Powell, Convergence properties of a class of minimization algorithms, in Nonlinear Pro-gramming, O. L. Mangasarian, R. R. Meyer and S. M. Robinson (eds.), Academic Press, New York, 1975, 1-27.

[14] A.A. Ribeiro and E.W. Karas, Continuous Optimization:Theoretical and Computational Aspects (in Portuguese), Cengage Learning, 2013.

[15] T. Steihaug, The conjugate gradient method and trust regions inlarge scale optimization, SIAM J. Numer. Anal., 20(1983), 626-637.

[16] Y.X. Yuan, Nonlinear Programming:trust region algorithms, in Proceedings of Chinese SIAM annual meeting, S.T. Xiao and F. Wu (eds.), Tsinghua University, Beijing, 1994, 83-97.

[17] Y.X. Yuan and W.Y. Sun, Optimization Theories and Methods (in Chinese), Science Press, Beijing, 1997.

[18] Y.X. Yuan, Recent advance in trust region algorithms, Mathematical Programming Series B, 151(2015), 249-281.
[1] Oleg Burdakov, Yuhong Dai, Na Huang. STABILIZED BARZILAI-BORWEIN METHOD [J]. Journal of Computational Mathematics, 2019, 37(6): 916-936.
[2] Zorana Lužanin, Irena Stojkovska, Milena Kresoja. DESCENT DIRECTION STOCHASTIC APPROXIMATION ALGORITHM WITH ADAPTIVE STEP SIZES [J]. Journal of Computational Mathematics, 2019, 37(1): 76-94.
[3] Yunfeng Cai, Zhaojun Bai, John E. Pask, N. Sukumar. CONVERGENCE ANALYSIS OF A LOCALLY ACCELERATED PRECONDITIONED STEEPEST DESCENT METHOD FOR HERMITIAN-DEFINITE GENERALIZED EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2018, 36(5): 739-760.
[4] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[5] Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM [J]. Journal of Computational Mathematics, 2012, 30(3): 262-278.
[6] Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION [J]. Journal of Computational Mathematics, 2011, 29(3): 261-286.
[7] Qun-yan Zhou,Wen-yu Sun. A NONMONOTONE SECOND-ORDER STEPLENGTH METHOD FOR UNCONSTRAINEDMINIMIZATION [J]. Journal of Computational Mathematics, 2007, 25(1): 104-112.
[8] Qun-yan Zhou,Wen-yu Sun. AN ADAPTIVE NONMONOTONIC TRUST REGION METHOD WITH CURVILINEAR SEARCHES [J]. Journal of Computational Mathematics, 2006, 24(6): 761-770.
[9] Chang-yin Zhou,Guo-ping He,Yong-li Wang . A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 591-608.
[10] Lei-hong Zhang,Ping-qi Pan. A GENERALIZED QUASI-NEWTON EQUATION AND COMPUTATIONAL EXPERIENCE [J]. Journal of Computational Mathematics, 2006, 24(5): 665-674.
[11] Ya-xiang Yuan. A NEW STEPSIZE FOR THE STEEPEST DESCENT METHOD [J]. Journal of Computational Mathematics, 2006, 24(2): 149-156.
[12] Cheng-xian Xu, Yue-ting Yang. Convergence Properties of Multi-directional Parallel Algorithms for Unconstrained Minimization [J]. Journal of Computational Mathematics, 2005, 23(4): 357-372.
[13] Xin-long Luo. Singly Diagonally Implicit Runge-Kutta Methods Combining Line Search Techniques for Unconstrained Optimization [J]. Journal of Computational Mathematics, 2005, 23(2): 153-164.
[14] Wei Wang, Lian-sheng Zhang, Yi-fan Xu . A Revised Conjugate Gradient Projection Algorithm for Inequality Constrained Optimizations [J]. Journal of Computational Mathematics, 2005, 23(2): 217-224.
[15] Jin Yan FAN,Wen Bao AI,Qun Ying ZHANG. A LINE SEARCH AND TRUST REGION ALGORITHM WITH TRUST REGION RADIUS CONVERGING TO ZERO [J]. Journal of Computational Mathematics, 2004, 22(6): 865-872.
Viewed
Full text


Abstract