×

An efficient conjugate gradient method with strong convergence properties for non-smooth optimization. (English) Zbl 1499.90129

Summary: In this paper, we introduce an efficient conjugate gradient method for solving nonsmooth optimization problems by using the Moreau-Yosida regularization approach. The search directions generated by our proposed procedure satisfy the sufficient descent property, and more importantly, belong to a suitable trust region. Our proposed method is globally convergent under mild assumptions. Our numerical comparative results on a collection of test problems show the efficiency and superiority of our proposed method. We have also examined the ability and the effectiveness of our approach for solving some real-world engineering problems from image processing field. The results confirm better performance of our method.

MSC:

90C06 Large-scale problems in mathematical programming
90C26 Nonconvex programming, global optimization
65Y20 Complexity and performance of numerical algorithms

Software:

SCALCG; LDGB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Andrei,Numerical comparison of conjugate gradient algorithms for unconstrained optimization, Stud. Inform. Control.16(2007) 333-352.
[2] N. Andrei,Conjugate gradient algorithms for unconstrained optimization. A survey on their definition,Tech. rep., ICI Technical Report, 2008.
[3] N. Andrei,A numerical study on efficiency and robustness of some conjugate gradient algorithms for large-scale unconstrained optimization, Stud. Inform. Control.22(2013)259- 284.
[4] X. Chen, M. Fukushima,Proximal quasi-newton methods for nondifferentiable convex optimization, Math. Program.85(1999) 313-334. · Zbl 0946.90111
[5] A.R. Conn, N.I. Gould, P.L. Toint,Trust Region Methods, SIAM, Philadelphia, 2000. · Zbl 0958.65071
[6] R. Correa, C. Lemar´echal,Convergence of some algorithms for convex minimization, Math. Program.62(1993) 261-275. · Zbl 0805.90083
[7] Y.H. Dai, L.Z. Liao,New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim.43(2001) 87-101. · Zbl 0973.65050
[8] Y.H. Dai, Y. Yuan,A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim.10(1999) 177-182. · Zbl 0957.65061
[9] M. Fatemi,A new efficient conjugate gradient method for unconstrained optimization, J. Comput. Appl. Math.300(2016) 207-216. · Zbl 1382.65170
[10] R. Fletcher,Practical Methods of Optimization, John Wiley & Sons, 2013. · Zbl 0905.65002
[11] R. Fletcher, C.M. Reeves,Function minimization by conjugate gradients, Comput. J.7 (1964) 149-154. · Zbl 0132.11701
[12] M. Fukushima,A descent algorithm for nonsmooth convex optimization, Math. Program. 30(1984) 163-175. · Zbl 0545.90082
[13] M. Fukushima, L. Qi,A globally and superlinearly convergent algorithm for nonsmooth convex minimization, SIAM J. Optim.6(1996) 1106-1120. · Zbl 0868.90109
[14] M. Haarala, K. Miettinen, M.M M¨akel¨a,New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw.19(2004) 673-692. · Zbl 1068.90101
[15] W.W. Hager, H. Zhang,A survey of nonlinear conjugate gradient methods, Pac. J. Optim. 2(2006) 35-58. · Zbl 1117.90048
[16] P.C. Hansen, J.G. Nagy, D.P. O’leary,Deblurring Images: Matrices, Spectra, and Filtering, SIAM, Philadelphia, 2006. · Zbl 1112.68127
[17] M.R. Hestenes, E. Stiefel,Methods of Conjugate Gradients for Solving Linear Systems, NBS Washington, DC, 1952. · Zbl 0048.09901
[18] J.B. Hiriart-Urruty, C. Lemar´echal,Acceleration of the Cutting-Plane Algorithm: Primal Forms of Bundle Methods, Springer, 1993.
[19] J.B. Hiriart-Urruty and C. Lemar´echal,Convex analysis and minimization algorithms I: Fundamentals, Springer science & business media, 2013.
[20] Y. Hu,Multivariate spectral gradient algorithm for nonsmooth convex optimization problems, E Math. Probl. Eng.2015(2015) 145323. · Zbl 1394.90456
[21] X. Jiang, J. Jian,Improved Fletcher-Reeves and Dai-Yuan conjugate gradient methods with the strong Wolfe line search, J. Comput. Appl. Math.348(2019) 525-534. · Zbl 1409.90092
[22] N. Karmitsa, A. Bagirov, M.M. M¨akel¨a,Comparing different nonsmooth minimization methods and software, Optim. Methods Softw.27(2012) 131-153. · Zbl 1242.90233
[23] C. Lemar´echal, C. Sagastiz´abal,Practical aspects of the Moreau-Yosida regularization: Theoretical preliminaries, SIAM J. Optim.7(1997) 367-385. · Zbl 0876.49019
[24] Q. Li,Conjugate gradient type methods for the nondifferentiable convex minimization, Optim. Lett7(2013) 533-545. · Zbl 1287.90049
[25] Li,A modified Fletcher-Reeves-type method for nonsmooth Convex Minimization, Stat. Optim. Inform. Comput.2(2014) 200-210.
[26] Y. Liu, C. Storey,Efficient generalized conjugate gradient algorithms, part 1: Theory, J. Optim. Theory Appl.69(1991) 129-137. · Zbl 0702.90077
[27] S. Lu, Z. Wei, L. Li,A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization, Comput. Optim. Appl.51(2012) 551-573. · Zbl 1268.90048
[28] L. Lukˇsan, J. Vlcek,Test problems for nonsmooth unconstrained and linearly constrained optimization, Technick´a zpr´ava, 2000.
[29] F. Meng, G. Zhao,On second-order properties of the Moreau-Yosida regularization for constrained nonsmooth convex programs, Numer. Funct. Anal. Optim.25(2004) 515-529. · Zbl 1071.90030
[30] N. Parikh, S. Boyd,Proximal algorithms, Foundations Trends. Optim.1(2013) 123-231.
[31] B.T. Polyak,The conjugate gradient method in extremal problems, Comput. Math. Math. Phys.9(1969) 94-112. · Zbl 0229.49023
[32] L. Qi,Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res.18(1993) 227-244. · Zbl 0776.65037
[33] A. Rauf, M. Fukushima,Globally convergent BFGS method for nonsmooth convex optimization1, J. Optim. Theory Appl.104(2000) 539-558. · Zbl 0986.90076
[34] N. Sagara, M. Fukushima,A trust region method for nonsmooth convex optimization, Management1(2005) 171-180. · Zbl 1177.90319
[35] Z. Wei, L. Ql,Convergence analysis of a proximal newton method: Analysis of a proximal Newton method, Numer. Funct. Anal. Optim.17(1996) 463-472. · Zbl 0884.90123
[36] T.G. Woldu, H. Zhang, Y.H. Fissuh,A modified nonlinear conjugate gradient algorithm for large-scale nonsmooth convex optimization, J. Optim. Theory Appl.185(2020) 1-16. · Zbl 1441.90159
[37] G. Yuan, T. Li, W. Hu,A conjugate gradient algorithm and its application in large-scale optimization problems and image restoration, J. Inequal. Appl.1(2019) 247-258. · Zbl 1499.90131
[38] G. Yuan, Z. Meng, Y. Li,A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, J. Optim. Theory Appl.168 (2016) 129-152. · Zbl 1332.65081
[39] G. Yuan, Z. Wei,The Barzilai and Borwein gradient method with nonmonotone line search for nonsmooth convex optimization problems, Math. Model. Anal.17(2012) 203-216. · Zbl 1242.90170
[40] G. Yuan, Z. Wei, G. Li,A modified Polak-Ribi‘ere-Polyak conjugate gradient algorithm for nonsmooth convex programs, J. Comput. Appl. Math.255(2014) 86-96. · Zbl 1291.90315
[41] G. Yuan, Z. Wei, Z. Wang,Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization, Comput. Optim. Appl.54(2013) 45-64. · Zbl 1267.90101
[42] L.U. Yuzhen,Out-of-focus blur: Image deblurring, arXiv:1710.00620, 2017.
[43] L. Zhang,A new trust region algorithm for nonsmooth convex minimization, Appl. Math. Comput.193(2007) 135 · Zbl 1193.90171
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.