A Hybrid Conjugate Gradient Algorithm for Nonconvex Functions and Its Applications in Image Restoration Problems

doi:10.1007/s40305-022-00424-6

Abstract

Abstract: It is prominent that conjugate gradient method is a high-efficient solution way for large-scale optimization problems. However, most of the conjugate gradient methods do not have sufficient descent property. In this paper, without any line search, the presented method can generate sufficient descent directions and trust region property. While use some suitable conditions, the global convergence of the method is established with Armijo line search. Moreover, we study the proposed method for solving nonsmooth problems and establish its global convergence. The experiments show that the presented method can be applied to solve smooth and nonsmooth unconstrained problems, image restoration problems and Muskingum model successfully.

Key words: Conjugate gradient, Smooth and nonsmooth problems, Nonconvex functions, Global convergence

CLC Number:

90C06
90C26

Gong-Lin Yuan, Ying-Jie Zhou, Meng-Xiang Zhang. A Hybrid Conjugate Gradient Algorithm for Nonconvex Functions and Its Applications in Image Restoration Problems[J]. Journal of the Operations Research Society of China, 2023, 11(4): 759-781.

TrendMD

References

[1] Andrei, N.: An adaptive scaled BFGS method for unconstrained optimization. Numer. Algorithms 77, 413-432 (2018)
[2] Yuan, G., Sheng, Z., Wan, B.: The global convengence of a modified BFGS method for nonconvex functions. J. Comput. Appl. Math. 327, 470-495 (2018)
[3] Grippo, L., Lucidi, S.: A globally convergent version of the Polak-Ribire-Polyak conjugate gradient method. Math. Program. 78, 375-391 (1997)
[4] Wei, Z., Li, G., Qi, L.: New nonlinear conjugate gradient formular for large-scale unconstrained optimization problems. Appl. Math. Comput. 179, 407-430 (2006)
[5] Zhang, L.: A new Liu-Storey type nonlinear conjugate gradient method for unconstrained optimization problems. J. Comput. Appl. Math. 225, 146-157 (2009)
[6] Yuan, G., Lu, J., Wang, Z.: The modified PRP conjugate gradient algorithm under a non-descent line search and its application in the Muskingum model and image restoration problems. Soft. Comput. 25, 5867-5879 (2021)
[7] Du, S., Chen, Y.: Global convergence of a modified spectral FR conjugate gradient method. Appl. Math. Comput. 202, 766-770 (2008)
[8] Sellami, B., Laskri, Y., Benzine, R.: A new two-parameter famliy of nonlinear conjugate gradient methods. Optimization 64, 993-1009 (2015)
[9] Fletcher, R., Reeves, C.: Function minimization by conjugate gradients. Comput. J. 7, 149-154 (1964)
[10] Polak, E., Ribière, G.: Note sur la convergence de directions conjuges. Rev. Franaise Informat. Recherche Opertionelle, 3e année 16, 35-43 (1969)
[11] Dai, Y., Yuan, Y.: A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim. 10, 177-182 (2000)
[12] Liu, Y., Storey, C.: Efficient generalized conjugate gradient for sovling linear systems. J. Optim. Theory Appli. 69, 129-131 (1991)
[13] Hestenes, M., Stiefel, E.: Method of conjugate gradient algorithms, part 1: theory. J. Res. Natl. Bur. Stand. 49, 409-432 (1952)
[14] Fletcher, R.: Unconstrained optimization. In: Pratical Method Optim., John Wiley & Sons (1987)
[15] Zhang, L., Zhou, W., Li, D.: A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA J. Numer. Anal. 26, 629-640 (2006)
[16] Yuan, G., Zhang, M.: A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations. J. Comput. Appl. Math. 286, 186-195 (2015)
[17] Li, M., Li, D.: A modified conjugate descent method and its global convergence. Pac. J. Optim. 2, 247-259 (2012)
[18] Yuan, G., Li, T., Hu, W.: A conjugate gradient algorithm for large-scale nonlinear equations and image restoration problems. Appl. Numer. Math. 147, 129-141 (2020)
[19] Li, M., Qu, A.: Some sufficient descent conjugate gradient methods and their global convergence. J. Comput. Appl. Math. 33, 333-347 (2014)
[20] Ahmed, T., Storey, C.: Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl. 64, 379-397 (1990)
[21] Andrei, N.: A bybrid conjugate algorithm for unconstrained optimization as a convex combination of Hestenes-Stifel and Dai-Yuan. Studies in Informatics and Control (2008)
[22] Jian, J., Han, L., Jiang, X.: A hybrid conjugate gradient method with descent property for unconstrained optimization. Appl. Math. Model. 39, 1281-1290 (2015)
[23] Andrei, N.: Hybrid conjugate gradient algorithm for unconstrained optimization. J. Optim. Theory Appl. 141, 249-264 (2009)
[24] Yuan, G., Lu, J., Wang, Z.: The PRP conjugate algorithm with a modified WWP line search and its application in restoration problems. Appl. Numer. Math. 152, 1-11 (2020)
[25] Yuan, G., Wei, Z., Lu, X.: Global convergence of the BFGS method and the PRP method for general functions under a modified weak Wolfe-Powell line search. Appl. Math. Model. 47, 811-825 (2017)
[26] Dai, Z., Wen, F.: Global convergence of a modified Hestenes-Stiefel nonlinear conjugate gradient method with Armijo line search. Numer. Algorithms 59, 79-93 (2012)
[27] Wei, Z., Yu, G., Yuan, G., Lian, Z.: The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Comput. Optim. Appl. 29, 315-332 (2004)
[28] Birgin, E., Martnez, J.: A spectral conjugate gradient method for unconstrained optimization. Appl. Math. Optim. 43, 117-128 (2001)
[29] Li, D., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15-35 (2001)
[30] Rockafellar, R.: Monotone operators and proximal point algorithm. SIAM J. Control. Optim. 14, 877-898 (1976)
[31] Kiwiel, K.: Proximal control in bundel methods for convex nondifferentiable optimization. Math. Program. 46, 105-199 (1990)
[32] Schramm, H.: Eine kombination von Bundle-und Trust-Region-Verfahren zur Lösung nichtdifferenzierbare Optimierungsproblrme. Bayreuther Mathematische Schriften, Heft 40, University Bayreuth (1989)
[33] Wolfe, P.: A method of conjugate subgradients for minimizing nondifferentiable convex functions. Math. Program. Study 3, 145-173 (1975)
[34] Yuan, G., Wei, Z., Wang, Z.: Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization. Comput. Optim. Appl. 54, 45-64 (2013)
[35] Wujie, Hu., Jinzhao, Wu., Yuan, Gonglin: Some modified Hestenes-Stiefel conjugate gradient algorithms with applications in image restoration. Appl. Numer. Math. 158, 360-376 (2020)
[36] Yuan, G., Meng, Z., Li, Y.: A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations. J. Optim. Theory Appl. 168, 129-152 (2016)
[37] Yuan, G., Wei, Z., Li, G.: A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs. J. Comput. Appl. Math. 255, 86-96 (2014)
[38] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227-245 (1993)
[39] Fukushima, M., Qi, L.: A globally and superlinearly convergent algorithm for nonsmooth convex minimization. SIAM J. Optim. 6, 1106-1120 (1996)
[40] Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim 10, 147-161 (2008)
[41] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002)
[42] Ouyang, A., Liu, L., Sheng, Z., Wu, F.: A class of parameter estimation methods for nonlinear Muskingum model using hybrid invasive weed optimization algorithm. Math. Probl. Eng. 2015, 1-15 (2015)
[43] Ouyang, A., Tang, Z., Li, K., Sallam, A., Sha, E.: Estimating parameters of Muskingum model using an adaptive hybrid PSO algorithm. Int. J. Pattern Recongnition Artif. Intell. 28, 1-29 (2014)
[44] Geem, Z.W.: Paramter estimation for the nonlinear Muskingum model using the BFGS technique. J. Irrig. Drain. Eng. 132, 474-478 (2006)