An accelerated conjugate gradient algorithm for solving nonlinear monotone equations and image restoration problems. (English) Zbl 1459.65062
Summary: Combining the three-term conjugate gradient method of Yuan and Zhang and the acceleration step length of Andrei with the hyperplane projection method of Solodov and Svaiter, we propose an accelerated conjugate gradient algorithm for solving nonlinear monotone equations in this paper. The presented algorithm has the following properties: (i) All search directions generated by the algorithm satisfy the sufficient descent and trust region properties independent of the line search technique. (ii) A derivative-free search technique is proposed along the direction to obtain the step length \(\alpha_k\). (iii) If \(\phi_k=- \alpha_k \left( h_k - h \left( w_k\right)\right)^T d_k>0\), then an acceleration scheme is used to modify the step length in a multiplicative manner and create a point. (iv) If the point satisfies the given condition, then it is the next point; otherwise, the hyperplane projection technique is used to obtain the next point. (v) The global convergence of the proposed algorithm is established under some suitable conditions. Numerical comparisons with other conjugate gradient algorithms show that the accelerated computing scheme is more competitive. In addition, the presented algorithm can also be applied to image restoration.
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 90C30 | Nonlinear programming |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
References:
| [1] | Dirkse, S. P.; Ferris, M. C., MCPLIB: a collection of nonlinear mixed complementarity problems, Optimization Methods and Software, 5, 4, 319-345 (1995) · doi:10.1080/10556789508805619 |
| [2] | Griewank, A., The “global” convergence of Broyden-like methods with suitable line search, The Journal of the Australian Mathematical Society. Series B. Applied Mathematics, 28, 1, 75-92 (1986) · Zbl 0596.65034 · doi:10.1017/s0334270000005208 |
| [3] | Grippo, L.; Sciandrone, M., Nonmonotone derivative-free methods for nonlinear equations, Computational Optimization and Applications, 37, 3, 297-328 (2007) · Zbl 1180.90310 · doi:10.1007/s10589-007-9028-x |
| [4] | Li, D.; Fukushima, M., A derivative-free line search and DFP method for symmetric equations with global and superlinear convergence, Numerical Functional Analysis and Optimization, 20, 1-2, 59-77 (1999) · Zbl 0927.65067 |
| [5] | Li, D.; Fukushima, M., A globally and superlinearly convergent gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM Journal on Numerical Analysis, 37, 1, 152-172 (1999) · Zbl 0946.65031 · doi:10.1137/s0036142998335704 |
| [6] | Li, Q.; Li, D.-H., A class of derivative-free methods for large-scale nonlinear monotone equations, IMA Journal of Numerical Analysis, 31, 4, 1625-1635 (2011) · Zbl 1241.65047 · doi:10.1093/imanum/drq015 |
| [7] | Kiefer, S.; Luttenberger, M.; Esparza, J., On the convergence of Newton’s method for monotone systems of polynomial equations, Proceedings of the 39th Annual ACM Symposium on Theory of Computing · doi:10.1145/1250790.1250822 |
| [8] | Silva, G. N., Local convergence of Newton’s method for solving generalized equations with monotone operator, Applicable Analysis, 97, 7, 1094-1105 (2018) · Zbl 1461.65107 · doi:10.1080/00036811.2017.1299860 |
| [9] | Yuan, G.; Wei, Z.; Lu, S., Limited memory BFGS method with backtracking for symmetric nonlinear equations, Mathematical and Computer Modelling, 54, 1-2, 367-377 (2011) · Zbl 1225.65056 · doi:10.1016/j.mcm.2011.02.021 |
| [10] | Zhang, B.; Zhu, Z., A modified quasi-Newton diagonal update algorithm for total variation denoising problems and nonlinear monotone equations with applications in compressive sensing, Numerical Linear Algebra with Applications, 22, 3, 500-522 (2015) · Zbl 1363.65096 · doi:10.1002/nla.1968 |
| [11] | Zhou, W.-J.; Li, D.-H., A globally convergent BFGS method for nonlinear monotone equations without any merit functions, Mathematics of Computation, 77, 264, 2231-2240 (2008) · Zbl 1203.90180 · doi:10.1090/s0025-5718-08-02121-2 |
| [12] | Zhou, W.; Li, D., Limited memory BFGS method for nonlinear monotone equations, Journal of Computational and Applied Mathematics, 25, 1, 89-96 (2007) |
| [13] | Zhou, G.; Toh, K. C., Superlinear convergence of a Newton-type algorithm for monotone equations, Journal of Optimization Theory and Applications, 125, 1, 205-221 (2005) · Zbl 1114.65055 · doi:10.1007/s10957-004-1721-7 |
| [14] | Qiu, Y.; Ying, C.; Lei, L., Multivariate spectral conjugate gradient projection method for nonlinear monotone equations, Proceedings of the 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies (EIDWT) |
| [15] | Zhang, L.; Zhou, W., Spectral gradient projection method for solving nonlinear monotone equations, Journal of Computational and Applied Mathematics, 196, 2, 478-484 (2006) · Zbl 1128.65034 · doi:10.1016/j.cam.2005.10.002 |
| [16] | Hu, Y.; Wei, Z., Wei-yao-liu conjugate gradient projection algorithm for nonlinear monotone equations with convex constraints, International Journal of Computer Mathematics, 92, 11, 1-12 (2015) · Zbl 1335.90067 · doi:10.1080/00207160.2014.977879 |
| [17] | Wang, X. Y.; Li, S. J.; Kou, X. P., A self-adaptive three-term conjugate gradient method for monotone nonlinear equations with convex constraints, Calcolo, 53, 2, 133-145 (2016) · Zbl 1338.90459 · doi:10.1007/s10092-015-0140-5 |
| [18] | Liu, S.-Y.; Huang, Y.-Y.; Jiao, H.-W., Sufficient descent conjugate gradient methods for solving convex constrained nonlinear monotone equations, Abstract and Applied Analysis, 2014, 1, 1-12 (2014) · Zbl 1470.65104 · doi:10.1155/2014/305643 |
| [19] | Yuan, G.; Hu, W., A conjugate gradient algorithm for large-scale unconstrained optimization problems and nonlinear equations, Journal of Inequalities and Applications, 2018, 1, 113 (2018) · Zbl 1497.90162 · doi:10.1186/s13660-018-1703-1 |
| [20] | Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49, 6, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [21] | Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, The Computer Journal, 7, 2, 149-154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 |
| [22] | Polak, E.; Ribière, G., Note sur la convergence de méthodes de directions conjuguées, Revue française d’informatique et de recherche opérationnelle. Série rouge, 3, 16, 35-43 (1969) · Zbl 0174.48001 · doi:10.1051/m2an/196903r100351 |
| [23] | Polyak, B. T., The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9, 4, 94-112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4 |
| [24] | Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms, part 1: theory, Journal of Optimization Theory and Applications, 69, 1, 129-137 (1991) · Zbl 0702.90077 · doi:10.1007/bf00940464 |
| [25] | Fletcher, R., Practical Method of Optimization Vol. I: Unconstrained Optimization (1987), New York, NY, USA: John Wiley and Sons, New York, NY, USA · Zbl 0905.65002 |
| [26] | Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10, 1, 177-182 (1999) · Zbl 0957.65061 · doi:10.1137/s1052623497318992 |
| [27] | Zhang, L.; Zhou, W.; Li, D.-H., A descent modified polak-ribière-polyak conjugate gradient method and its global convergence, IMA Journal of Numerical Analysis, 26, 4, 629-640 (2006) · Zbl 1106.65056 · doi:10.1093/imanum/drl016 |
| [28] | Yuan, G.; Zhang, M., A three-terms polak-ribière-polyak conjugate gradient algorithm for large-scale nonlinear equations, Journal of Computational and Applied Mathematics, 286, 186-195 (2015) · Zbl 1316.90038 · doi:10.1016/j.cam.2015.03.014 |
| [29] | Ahookhosh, M.; Amini, K.; Bahrami, S., Two derivative-free projection approaches for systems of large-scale nonlinear monotone equations, Numerical Algorithms, 64, 1, 21-42 (2013) · Zbl 1290.65046 · doi:10.1007/s11075-012-9653-z |
| [30] | Koorapetse, M.; Kaelo, P., Globally convergent three-term conjugate gradient projection methods for solving nonlinear monotone equations, Arabian Journal of Mathematics, 7, 1, 1-13 (2018) · Zbl 1412.90142 · doi:10.1007/s40065-018-0206-8 |
| [31] | Liu, J. K.; Li, S. J., A projection method for convex constrained monotone nonlinear equations with applications, Computers & Mathematics with Applications, 70, 10, 2442-2453 (2015) · Zbl 1443.65073 · doi:10.1016/j.camwa.2015.09.014 |
| [32] | Liu, J.; Li, S.; Li, S., Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations, Journal of Industrial & Management Optimization, 13, 1, 283-295 (2017) · Zbl 1368.49038 · doi:10.3934/jimo.2016017 |
| [33] | Goldstein, A. A., Convex programming in hilbert space, Bulletin of the American Mathematical Society, 70, 5, 709-711 (1964) · Zbl 0142.17101 · doi:10.1090/s0002-9904-1964-11178-2 |
| [34] | Solodov, M.; Svaiter, B., A globally convergent inexact Newton method for systems of monotone equations, Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, 355-369 (1998), New York, NY, USA: Kluwer Academic Publishers, New York, NY, USA · Zbl 0928.65059 |
| [35] | Andrei, N., Another conjugate gradient algorithm with guaranteed descent and conjugacy conditions for large-scale unconstrained optimization, Journal of Optimization Theory and Applications, 159, 1, 159-182 (2013) · Zbl 1275.90090 · doi:10.1007/s10957-013-0285-9 |
| [36] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
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.
