A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

doi:10.4208/jcm.1907-m2018-0173

Journal of Computational Mathematics ›› 2021, Vol. 39 ›› Issue (2): 159-177.DOI: 10.4208/jcm.1907-m2018-0173

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

Keke Zhang¹, Hongwei Liu¹, Zexian Liu²

1. School of Mathematics and Statistics, Xidian University, Xi'an 710126, China;
2. State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering computing, AMSS, Chinese Academy of Sciences, Beijing 100190, China

Received:2018-08-10 Revised:2019-02-18 Online:2021-03-15 Published:2021-03-15
Contact: Zexian Liu,Email:liuzexian2008@163.com
Supported by:
We would like to thank the editor and the anonymous referees for their valuable comments, which are helpful to improve the quality of this paper. We would like to thank Professor Dai Y.H. and Dr. Kou C.X. for their CGOPT code, and thank Professors Hager W.W. and Zhang H.C. for their CG DESCENT(5.3) code. This research is supported by National Science Foundation of China (No. 11901561), China Postdoctoral Science Foundation (2019M660833) and Guangxi Natural Science Foundation (No. 2018GXNSFBA281180).

PDF ( 54 ) Cited

Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION[J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.

A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper. The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces, and we also proposed an adaptive rule for choosing different searching directions at each iteration. We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition. With the used nonmonotone line search, we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions. Numerical experiments show that the proposed algorithm is promising for the given test problem set.

Key words: Conjugate gradient method, Nonmonotone line search, Subspace minimization, Sufficient descent condition, Global convergence

CLC Number:

90C30

[1] Y.H. Dai, J.Y. Han, G.H. Liu, D.F. Sun, H.X. Yin and Y.X. Yuan, Convergence properties of nonlinear conjugate gradient methods. SIAM J. Optim., 10:2(1999), 345-358.
[2] W.W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods. Pac. J. Optim., 2:1(2006), 35-38.
[3] N. Andrei, Numerical comparison of conjugate gradient algorithms for unconstrained optimization. Stud. Inform. Control., 16:4(2007), 333-352.
[4] R. Fletcher and C.M. Reeves, Function minimization by conjugate gradients. Comput. J., 7:2(1964), 149-154.
[5] E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées. Rev. Francaise Inform. Rech. Opérationnelle, 3:16(1969), 35-34.
[6] B.T. Polyak, The conjugate gradient method in extremal problems. USSR Comput. Math. Math. Phys., 9:4(1969), 94-112.
[7] M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand., 49:6(1952), 409-436.
[8] Y.H. Dai and Y.X. Yuan, A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim., 10:1(1999), 177-182.
[9] Y.H. Dai, Nonlinear conjugate gradient methods. John Wiley, 2011, 1-36. https://doi.org/10.1002/9780470400531.eorms0183.
[10] P. Radosaw, Conjugate gradient algorithm in nonconvex optimization. Springer-Verlag, Berlin Heidelberg, 2009.
[11] Y.H. Dai and C.X. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM J. Optim., 23:1(2013), 296-320.
[12] W.W. Hager and H. Zhang, A new conjugate gradient method with guarantee descent and an efficient line search. SIAM J. Optim., 16:1(2005), 170-192.
[13] H. Zhang and W.W. Hager, A nonmomotone line search technique and its application to unconstrained optimization. SIAM J. Optim., 14:4(2004), 1043-1056.
[14] E.M.L. Beale, A derivative of conjugate-gradients In:Lootsma, F.A (ed.), Numerical Methods for Nonlinear Optimization, Academic Press, London, 1972, 39-43.
[15] L. Nazareth, A conjugate direction algorithm without line search, J. Optimiz. Theory App., 23:3(1997), 373-387.
[16] L. Zhang, W. Zhou and D. Li, A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA J. Numer. Anal., 26:4(2006), 629-640.
[17] L. Zhang, W. Zhou and D.H. Li, Some descent three-term conjugate gradient methods and their global convergence. Optim. Methods Softw., 22:4(2007), 697-711.
[18] N. Andrei, A simple three-term conjugate gradient algorithm for unconstrained optimization. J. Comput. Appl. Math., 241(2013), 19-29.
[19] Y. Narushima, H. Yabe and J.A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim., 21:1(2011), 212-230
[20] X. L. Dong, H. W. Liu and Y. B. He, New version of the three-term conjugate gradient method based on spectral scaling conjugacy condition that generates descent search direction. Appl. Math. Comput., 269:15(2015), 606-617.
[21] N. Andrei, A modified Polak-Ribière-Polyak conjugate gradient algorithm for unconstrained optimization, Optimization, 60:12(2011), 1457-1471.
[22] Y.X. Yuan and J. Stoer, A subspace study on conjugate gradient algorithms. Zamm J. Appl. Mech. Z. Angew. Math. Mech., 75:1(1995), 69-77.
[23] N. Andrei, An accelerated subspace minimization three-term conjugate gradient algorithm for unconstrained optimization, Numer. Algor., 65:4(2014), 859-874.
[24] Y.H. Dai and C.X. Kou, New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Opt., 43:1(2001), 87-101.
[25] Y.T. Yang, Y.T. Chen and Y.L. Lu, A subspace conjugate gradient algorithm for large-scale unconstrained optimization. Numer. Algor., 76:3(2017), 813-828.
[26] Y.H., Dai and C.X. Kou, A Barzilai-Borwein conjugate gradient method. Sci. China Math., 59:8(2016), 1511-1524.
[27] H.W. Liu and Z.X. Liu:An efficient Barzilai-Borwein conjugate gradient method for unconstrained optimization. J Optim. Theory Appl., 180:3(2018), 879-906.
[28] M. Li, H.W. Liu and Z.X. Liu, A new subspace minimization conjugate gradient method with nonmonotone line search for unconstrained optimization. Numer. Algor., 79:1(2018), 195-219.
[29] W.W. Hager and H. Zhang, The limited memory conjugate gradient method. SIAM J. Optim., 23:4(2013), 2150-2168
[30] T. Wang, Z.X. Liu and H.W. Liu, A new subspace minimization conjugate gradient method based on tensor model for unconstrained optimization. Int. Comput, Math., 96:10(2019), 1924-1942.
[31] Y.F. Li, Z.X. Liu and H.W. Liu, A subspace minimization conjugate gradient method based on conic model for unconstrained optimization. Comut. Appl. Math., 38:16(2019), https://doi.org/10.1007/s40314-019-0779-7
[32] Y.X. Yuan, A review on subspace methods for nonlinear optimization. in Proceedings of the International Congress of Mathematics, (2014), 807-827.
[33] J. Barzilai and J.M. Borwein, Two-point step size gradient methods. IMA J. Numer. Anal., 8:1(1988), 141-148.
[34] N. Andrei, An unconstrained optimization test functions collection. Environ. Sci. Technol., 10:1(2008), 6552-6558.
[35] E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Prog., 91:2(2002), 201-213.
[36] W.W. Hager and H., Zhang, Algorithm 851:CG DESCENT, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Softw., 32:1(2006), 113-137.

[1]	Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2]	Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[3]	Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[4]	Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.
[5]	Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY [J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.
[6]	Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS [J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.
[7]	Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.
[8]	Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[9]	Houde Han, Chunxiong Zheng. POISSON PRECONDITIONING FOR SELF-ADJOINT ELLIPTIC PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(5): 560-578.
[10]	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.
[11]	Huangxin Chen, Xuejun Xu, Weiying Zheng. LOCAL MULTILEVEL METHODS FOR SECOND-ORDER ELLIPTIC PROBLEMS WITH HIGHLY DISCONTINUOUS COEFFICIENTS [J]. Journal of Computational Mathematics, 2012, 30(3): 223-248.
[12]	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.
[13]	El-Sayed M.E. Mostafa. A CONJUGATE GRADIENT METHOD FOR DISCRETE-TIME OUTPUT FEEDBACK CONTROL DESIGN [J]. Journal of Computational Mathematics, 2012, 30(3): 279-297.
[14]	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.
[15]	Junfeng Yin, Zhongzhi Bai . The Restrictively Preconditioned Conjugate Gradient Methods on NormalResidual for Block Two-by-Two Linear Systems [J]. Journal of Computational Mathematics, 2008, 26(2): 240-249.

Viewed

Full text

Abstract

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

扫码分享