×

zbMATH — the first resource for mathematics

A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing. (English) Zbl 1316.90050
Summary: \(\mathrm{CG}_{-}\mathrm{DESCENT}\) is a state-of-the-art algorithm to solve large-scale unconstrained minimization problems. However, research activities on \(\mathrm{CG}_{-}\mathrm{DESCENT}\) in some other scenarios are relatively fewer. In this paper, by combining with the projection method of M. V. Solodov and B. F. Svaiter [Appl. Optim. 22, 355–369 (1999; Zbl 0928.65059)], we extend \(\mathrm{CG}_{-}\mathrm{DESCENT}\) to solve large-scale nonlinear convex constrained monotone equations. The proposed method does not require the Jacobian information, even though it does not store any matrix at each iteration. It thus has the potential to solve large-scale non-smooth problems. Under some mild conditions, we show that the proposed method converges globally. Primary numerical results illustrate that the proposed method works quite well. Moreover, we also extend this method to solve the \(\ell_1\)-norm regularized problems to decode a sparse signal in compressive sensing. Performance comparisons show that the proposed method is practical, efficient and competitive with the compared ones.

MSC:
90C30 Nonlinear programming
90C25 Convex programming
Software:
CG_DESCENT
PDF BibTeX Cite
Full Text: DOI
References:
[1] An, X. M.; Li, D. H.; Xiao, Y., Sufficient descent directions in unconstrained optimization, Comput. Optim. Appl., 48, 515-532, (2011) · Zbl 1242.90223
[2] Barzilai, J.; Borwein, J. M., Two point step size gradient method, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055
[3] M. Figueiredo, R. Nowak, A bound optimization approach to wavelet-based image deconvolution, in: Proc. IEEE Int. Conf. Image Processing, ICIP’ 2005, 2005.
[4] Figueiredo, M.; Nowak, R.; Wright, S. J., Gradient projection for sparse reconstruction, application to compressed sensing and other inverse problems, IEEE J-STSP, 586-597, (2007), IEEE Press, Piscataway, NJ
[5] Hager, W. W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192, (2005) · Zbl 1093.90085
[6] Hager, W. W.; Zhang, H., Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software, 32, 113-137, (2006) · Zbl 1346.90816
[7] Iusem, A. N.; Solodov, M. V., Newton-type methods with generalized distance for constrained optimization, Optimization, 41, 257-278, (1997) · Zbl 0905.49015
[8] Li, D. H.; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129, 15-35, (2001) · Zbl 0984.65055
[9] Li, Q.; Li, D. H., A class of derivative-free methods for large-scale nonlinear monotone equations, IMA J. Numer. Anal., 31, 1625-1635, (2011) · Zbl 1241.65047
[10] Pang, J. S., Inexact Newton methods for the nonlinear complementary problem, Math. Program., 36, 54-71, (1986) · Zbl 0613.90097
[11] Solodov, M. V.; Svaiter, B. F., A globally convergent inexact Newton method for system of monotone equations, (Fukushima, M.; Qi, L., Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, (1999), Kluwer Academic Publishers), 355-369 · Zbl 0928.65059
[12] Wang, C.; Wang, Y.; Xu, C., A projection method for a system of nonlinear monotone equations with convex constraints, Math. Methods Oper. Res., 66, 33-46, (2007) · Zbl 1126.90067
[13] Xiao, Y.; Wang, Q.; Hu, Q., Non-smooth equations based method for \(\ell_1\)-norm problems with applications to compressed sensing, Nonlinear Anal. - Theory, 74, 3570-3577, (2011) · Zbl 1217.65069
[14] Yan, Q. R.; Peng, X. Z.; Li, D. H., A globally convergent derivative-free method for solving large-scale nonlinear monotone equations, J. Comput. Appl. Math., 234, 649-657, (2010) · Zbl 1189.65102
[15] Yu, Z.; Lin, J.; Sun, J.; Xiao, Y.; Liu, L.; Li, Z., Spectral gradient projection method for monotone nonlinear equations with convex constraints, Appl. Numer. Math., 59, 2416-2423, (2009) · Zbl 1183.65056
[16] Zhang, L.; Zhou, W. J., Spectral gradient projection method for solving nonlinear monotone equations, J. Comput. Appl. Math., 196, 478-484, (2006) · Zbl 1128.65034
[17] Zhao, Y. B.; Li, D., Monotonicity of fixed point and normal mapping associated with variational inequality and its application, SIAM J. Optim., 11, 962-973, (2001) · Zbl 1010.90084
[18] Zhou, W. J.; Li, D. H., Limited memory BFGS method for nonlinear monotone equations, J. Comput. Math., 25, 89-96, (2007)
[19] Zhou, W. J.; Li, D. H., A globally convergent BFGS method for nonlinear monotone equations without any merit functions, Math. Comp., 77, 2231-2240, (2008) · Zbl 1203.90180
[20] Zhou, G.; Toh, K. C., Superlinear convergence of a Newton-type algorithm for monotone equations, J. Optim. Theory Appl., 125, 205-221, (2005) · Zbl 1114.65055
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.