×

A modified spectral PRP conjugate gradient projection method for solving large-scale monotone equations and its application in compressed sensing. (English) Zbl 1435.65078

Summary: In this paper, we develop an algorithm to solve nonlinear system of monotone equations, which is a combination of a modified spectral PRP (Polak-Ribière-Polyak) conjugate gradient method and a projection method. The search direction in this algorithm is proved to be sufficiently descent for any line search rule. A line search strategy in the literature is modified such that a better step length is more easily obtained without the difficulty of choosing an appropriate weight in the original one. Global convergence of the algorithm is proved under mild assumptions. Numerical tests and preliminary application in recovering sparse signals indicate that the developed algorithm outperforms the state-of-the-art similar algorithms available in the literature, especially for solving large-scale problems and singular ones.

MSC:

65H10 Numerical computation of solutions to systems of equations
90C52 Methods of reduced gradient type
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

levmar
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Huang, S.; Wan, Z., A new nonmonotone spectral residual method for nonsmooth nonlinear equations, Journal of Computational and Applied Mathematics, 313, 82-101 (2017) · Zbl 1356.90139
[2] Wan, Z.; Guo, J.; Liu, J.; Liu, W., A modified spectral conjugate gradient projection method for signal recovery, Signal, Image and Video Processing, 12, 8, 1455-1462 (2018)
[3] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), New York, NY, USA: Siam, New York, NY, USA · Zbl 0241.65046
[4] Dennis, J. E.; Schnabel, B. R., Numerical methods for nonlinear equations and unconstrained optimization, Classics in Applied Mathematics, 16 (1983)
[5] Zhou, W.; Li, D., Limited memory {BFGS} method for nonlinear monotone equations, Journal of Computational Mathematics, 25, 1, 89-96 (2007)
[6] Martinez, J. M., A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM Journal on Numerical Analysis, 27, 4, 1034-1049 (1990) · Zbl 0702.65053
[7] Fasano, G.; Lampariello, F.; Sciandrone, M., A truncated nonmonotone Gauss-Newton method for large-scale nonlinear least-squares problems, Computational Optimization and Applications, 34, 3, 343-358 (2006) · Zbl 1122.90094
[8] 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
[9] Papp, Z.; Rapajić, S., FR type methods for systems of large-scale nonlinear monotone equations, Applied Mathematics and Computation, 269, 816-823 (2015) · Zbl 1410.65196
[10] Li, Q.; Li, D.-H., A class of derivative-free methods for large-scale nonlinear monotone equations, IMA Journal of Numerical Analysis (IMAJNA), 31, 4, 1625-1635 (2011) · Zbl 1241.65047
[11] Zhang, L.; Zhou, W.; Li, D. H., A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence, IMA Journal of Numerical Analysis (IMAJNA), 26, 4, 629-640 (2006) · Zbl 1106.65056
[12] La Cruz, W.; Martnez, J. M.; Raydan, M., Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Mathematics of Computation, 75, 255, 1429-1448 (2006) · Zbl 1122.65049
[13] Wan, Z.; Liu, W.; Wang, C., A modified spectral conjugate gradient projection method for solving nonlinear monotone symmetric equations, Pacific Journal of Optimization. An International Journal, 12, 3, 603-622 (2016) · Zbl 1349.90770
[14] 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
[15] Yan, Q.-R.; Peng, X.-Z.; Li, D.-H., A globally convergent derivative-free method for solving large-scale nonlinear monotone equations, Journal of Computational and Applied Mathematics, 234, 3, 649-657 (2010) · Zbl 1189.65102
[16] Amini, K.; Kamandi, A.; Bahrami, S., A double-projection-based algorithm for large-scale nonlinear systems of monotone equations, Numerical Algorithms, 68, 2, 213-228 (2015) · Zbl 1312.65079
[17] Li, Y.; Wan, Z.; Liu, J., Bi-level programming approach to optimal strategy for vendor-managed inventory problems under random demand, The ANZIAM Journal, 59, 2, 247-270 (2017) · Zbl 1390.90519
[18] Li, T.; Wan, Z., New adaptive Barzilar-Borwein step size and its application in solving large scale optimization problems, The ANZIAM Journal, 61, 1, 76-98 (2019) · Zbl 1409.90189
[19] Tong, X. J.; Qi, L., On the convergence of a trust-region method for solving constrained nonlinear equations with degenerate solutions, Journal of Optimization Theory and Applications, 123, 1, 187-211 (2004) · Zbl 1069.65055
[20] Levenberg, K., A method for the solution of certain non-linear problems in least squares, Quarterly of Applied Mathematics, 2, 164-168 (1944) · Zbl 0063.03501
[21] Marquardt, D., An algorithm for least-squares estimation of nonlinear parameters, SIAM Journal on Applied Mathematics, 11, 2, 431-441 (1963) · Zbl 0112.10505
[22] Kanzow, C.; Yamashita, N.; Fukushima, M., Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, Journal of Computational and Applied Mathematics, 173, 2, 321-343 (2005) · Zbl 1065.65070
[23] 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)
[24] 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
[25] Yuan, G.; Meng, Z.; Li, Y., A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, Journal of Optimization Theory and Applications, 168, 1, 129-152 (2016) · Zbl 1332.65081
[26] Yuan, G.; Hu, W., A conjugate gradient algorithm for large-scale unconstrained optimization problems and nonlinear equations, Journal of Inequalities and Applications, 2018, 1, article 113 (2018)
[27] 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
[28] Cheng, W., A PRP type method for systems of monotone equations, Mathematical and Computer Modelling, 50, 1-2, 15-20 (2009) · Zbl 1185.65088
[29] Solodov, M. V.; Svaiter, B. F., A globally convergent inexact Newton method for systems of monotone equations, Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, 355-369 (1998), Boston, MA, USA: Springer, Boston, MA, USA · Zbl 0928.65059
[30] Wan, Z.; Yang, Z.; Wang, Y., New spectral PRP conjugate gradient method for unconstrained optimization, Applied Mathematics Letters, 24, 1, 16-22 (2011) · Zbl 1208.49039
[31] Ou, Y.; Li, J., A new derivative-free SCG-type projection method for nonlinear monotone equations with convex constraints, Applied Mathematics and Computation, 56, 1-2, 195-216 (2018) · Zbl 1390.90521
[32] Zhou, W.; Li, D., On the Q-linear convergence rate of a class of methods for monotone nonlinear equations, Pacific Journal of Optimization, 14, 723-737 (2018)
[33] Polyak, B. T., Introduction to Optimization (1987), New York, NY, USA: Optimization Software, New York, NY, USA
[34] Xiao, Y.; Zhu, H., A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing, Journal of Mathematical Analysis and Applications, 405, 1, 310-319 (2013) · Zbl 1316.90050
[35] Xiao, Y.; Wang, Q.; Hu, Q., Non-smooth equations based method for \(l_1\) problems with applications to compressed sensing, Nonlinear Analysis. Theory, Methods and Applications, 74, 11, 3570-3577 (2011) · Zbl 1217.65069
[36] Kim, S.; Koh, K.; Lustig, M., A method for large-scale 1-regularized least squares problems with applications in signal processing and statistics, Technical Report (2007), Stanford, Calif, USA: Dept. of Electrical Engineering, Stanford University, Stanford, Calif, USA
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.