An accelerated descent CG algorithm with clustering the eigenvalues for large-scale nonconvex unconstrained optimization and its application in image restoration problems. (English) Zbl 1522.65101
Summary: Conjugate gradient methods are widely used for solving large-scale unconstrained optimization problems. Since they have the attractive practical factors of simple computation and low memory requirement, interesting theoretical features of curvature information and strong global convergence property. Based on the analysis of the minimization of the condition number and the positiveness of the corresponding matrix, we propose a choice for the parameter in Dai-Liao method and design a descent conjugate gradient algorithm which owns the sufficient descent property independent of the choices for line search techniques. Under some common conditions, the global convergence property for uniformly convex function and the general nonlinear function are established. In the numerical experiments, we firstly focus on 46 ill-conditioned matrix problems and present the corresponding primal results. Then 450 large-scale unconstrained problems are referred. Finally, we give an accelerated strategy for the proposed algorithm and apply it to some image restoration problems. Numerical results indicate that the algorithm is reliable and much more efficient and effective than the other methods for the test problems.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C06 | Large-scale problems in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C52 | Methods of reduced gradient type |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
conjugate gradient method; condition number; eigenvalue analysis; descent property; acceleration strategy; image restorationReferences:
| [1] | Dai, Y.; Han, J.; Liu, G.; Sun, D.; Yin, H.; Yuan, Y.-X., Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 2, 345-358 (2000) · Zbl 0957.65062 |
| [2] | Hager, W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pacific J. Optim., 2, 1, 35-58 (2006) · Zbl 1117.90048 |
| [3] | Andrei, N., Numerical comparison of conjugate gradient algorithms for unconstrained optimization, Stud. Inform. Control, 16, 4, 333-352 (2007) |
| [4] | Zhang, K.; Liu, H.; Liu, Z., A new Dai-Liao conjugate gradient method with optimal parameter choice, Numer. Funct. Anal. Optim., 40, 2, 194-215 (2019) · Zbl 1411.90329 |
| [5] | Dai, Y.; Liao, L., New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43, 1, 87-101 (2001) · Zbl 0973.65050 |
| [6] | Andrei, N., A Dai-Liao conjugate gradient algorithm with clustering of eigenvalues, Numer. Algorithms, 77, 1273-1282 (2018) · Zbl 06860411 |
| [7] | Andrei, N., Open problems in nonlinear conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl., 38, 3, 401-416 (2007) · Zbl 1168.90608 |
| [8] | Babaie-kafaki, S.; Ghanbari, R., The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices, Eur. J. Oper. Res., 234, 3, 625-630 (2014) · Zbl 1304.90216 |
| [9] | Babaie-Kafaki, S.; Ghanbari, R., A descent family of Dai-Liao conjugate gradient methods, Optim. Methods Softw., 29, 3, 583-591 (2014) · Zbl 1285.90063 |
| [10] | Peyghami, M.; Ahmadzadeh, H.; Fazli, A., A new class of efficient and globally convergent conjugate gradient methods in the Dai-Liao family, Optim. Methods Softw., 30, 4, 843-863 (2015) · Zbl 1328.90143 |
| [11] | Yao, S.; He, D.; Shi, L., An improved Perry conjugate gradient method with adaptive parameter choice, Numer. Algorithms, 78, 1255-1269 (2018) · Zbl 1396.65099 |
| [12] | Zheng, Y.; Zheng, B., Two new Dai-Liao-Type conjugate gradient methods for unconstrained optimization problems, J. Optim. Theory Appl., 175, 2, 502-509 (2017) · Zbl 1380.65108 |
| [13] | Khoshgam, Z.; Ashrafi, A., A new modified scaled conjugate gradient method for large-scale unconstrained optimization with non-convex objective function, Optim. Methods Softw., 34, 4, 783-796 (2018) · Zbl 1422.90023 |
| [14] | Hestenes, R.; Stiefel, L., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 6, 409-436 (1952) · Zbl 0048.09901 |
| [15] | Hager, W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 1, 170-192 (2005) · Zbl 1093.90085 |
| [16] | Dai, Y.; Kou, C., A nonlinear conjugate gradient algorithm with an optimal property and an improved wolfe line search, SIAM J. Optim., 23, 1, 296-320 (2013) · Zbl 1266.49065 |
| [17] | Biglari, F.; Hassan, M.; Leong, W., New quasi-Newton methods via higher order tensor models, J. Comput. Appl. Math., 235, 8, 2412-2422 (2011) · Zbl 1211.65068 |
| [18] | Wei, Z.; Li, G.; Qi, L., New quasi-Newton methods for unconstrained optimization problems, Appl. Math. Comput., 175, 2, 1156-1188 (2006) · Zbl 1100.65054 |
| [19] | Chen, L.; Deng, N.; Zhang, J., A modified quasi-Newton method for structured optimization with partial information on the Hessian, Comput. Optim. Appl., 35, 1, 5-18 (2006) · Zbl 1121.90126 |
| [20] | Babaie-kafaki, S., A modified scaled memoryless BFGS preconditioned conjugate gradient method for unconstrained optimization, 4OR-Q. J. Oper. Res., 11, 4, 361-374 (2013) · Zbl 1292.65061 |
| [21] | Yabe, H.; Takano, M., Global convergence properties of nonlinear conjugate gradient methods with modified secant condition, Comput. Optim. Appl., 28, 2, 203-225 (2004) · Zbl 1056.90130 |
| [22] | Yuan, G.; Wei, Z., Convergence analysis of a modified BFGS method on convex minimizations, Comput. Optim. Appl., 47, 2, 237-255 (2010) · Zbl 1228.90077 |
| [23] | Li, D.; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129, 1-2, 15-35 (2001) · Zbl 0984.65055 |
| [24] | Babaie-Kafaki, S.; Ghanbari, R., A modified scaled conjugate gradient method with global convergence for nonconvex functions, Bull. Belg. Math. Soc. Simon Stevin, 21, 3, 465-477 (2014) · Zbl 1305.90379 |
| [25] | Zhang, L.; Zhou, W.; Li, D., Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numer. Math., 104, 4, 561-572 (2006) · Zbl 1103.65074 |
| [26] | Babaie-Kafaki, S.; Ghanbari, R.; Mahdavi-Amiri, N., Two new conjugate gradient methods based on modified secant equations, J. Comput. Appl. Math., 234, 5, 1374-1386 (2010) · Zbl 1202.65071 |
| [27] | Gilbert, J.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 1, 21-42 (1992) · Zbl 0767.90082 |
| [28] | Livieris, I.; Pintelas, P., A descent Dai-Liao conjugate gradient method based on a modified secant equation and its global convergence, (ISRN Computational Mathematics (2012)), Article 435495 pp. · Zbl 1245.65067 |
| [29] | Watkins, S., Undamentals of Matrix Computations (2002), John Wiley and Sons: John Wiley and Sons New York · Zbl 1005.65027 |
| [30] | Babaie-Kafaki, S., A hybrid scaling parameter for the scaled memoryless BFGS method based on the \(\ell_\infty\) matrix norm, Int. J. Comput. Math., 96, 8, 1595-1602 (2019) · Zbl 1499.90214 |
| [31] | Andrei, N., An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 1, 147-161 (2008) · Zbl 1161.90486 |
| [32] | Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 |
| [33] | Andrei, N., An acceleration of gradient descent algorithm with backtracking for unconstrained optimization, Numer. Algorithms, 42, 1, 63-73 (2006) · Zbl 1101.65058 |
| [34] | Yu, G.; Huang, J.; Zhou, Y., A descent spectral conjugate gradient method for impulse noise removal, Appl. Math. Lett., 23, 5, 555-560 (2010) · Zbl 1186.94017 |
| [35] | Cai, J.; Chan, R.; Fiore, C., Minimization of a detail-preserving regularization functional for impulse noise removal, J. Math. Imaging Vision, 29, 1, 79-91 (2007) · Zbl 1523.94006 |
| [36] | Polyak, B. T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9, 4, 94-112 (1969) · Zbl 0229.49023 |
| [37] | Polak, E.; Ribière, G., Note sur la convergence de directions conjuguées, Rev. Fr. Autom. Inform. Rech. Oper., 16, 6, 35-43 (1969), (in French) · Zbl 0174.48001 |
| [38] | Yuan, G.; Wei, Z.; Lu, X., Global convergence of BFGS and PRP methods under a modified weak Wolfe-Powell line search, Appl. Math. Model., 47, 811-825 (2017) · Zbl 1446.65031 |
| [39] | Yuan, G.; Lu, J.; Wang, Z., The PRP conjugate gradient algorithm with a modified WWP line search and its application in the image restoration problems, Appl. Numer. Math., 152, 1-11 (2020) · Zbl 07173158 |
| [40] | Bovik, A., Handbook of Image and Video Processing (2000), Academic Press: Academic Press New York · Zbl 0967.68155 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
