zbMATH — the first resource for mathematics

A projection method for convex constrained monotone nonlinear equations with applications. (English) Zbl 1443.65073
Summary: In this paper, we present a projection method to solve monotone nonlinear equations with convex constraints. This method can be viewed as an extension of CG$$_-$$DESCENT method which is one of the most effective conjugate gradient methods for solving unconstrained optimization problems. Because of derivative-free and low storage, the proposed method can be used to solve large-scale nonsmooth monotone nonlinear equations. Its global convergence is established under some appropriate conditions. Preliminary numerical results show that the proposed method is effective and promising. Moreover, we also successfully use the proposed method to solve the sparse signal reconstruction in compressive sensing.

MSC:
 65H10 Numerical computation of solutions to systems of equations 90C53 Methods of quasi-Newton type
Software:
CoDoSol; levmar; MCPLIB; SPGL1; STRSCNE
Full Text:
References:
 [1] Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28, 549-560 (1974) · Zbl 0282.65042 [2] Dennis, J. E.; Moré, J. J., Quasi-Newton method, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041 [3] Brown, P. N.; Saad, Y., Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J. Optim., 4, 297-330 (1994) · Zbl 0814.65048 [4] Li, D.; Fukushima, M., A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J. Numer. Anal., 37, 152-172 (1999) · Zbl 0946.65031 [5] Zhou, G.; Toh, K. C., Superline convergence of a Newton-type algorithm for monotone equations, J. Optim. Theory Appl., 125, 205-221 (2005) · Zbl 1114.65055 [6] 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 [7] Zhou, W. J.; Li, D. H., Limited memory BFGS method for nonlinear monotone equations, J. Comput. Math., 25, 89-96 (2007) [8] yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, Computing, 15, 237-249 (2001), (Suppl.) · Zbl 1001.65047 [9] Kanzow, C.; Yamashita, N.; Fukushima, M., Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 173, 321-343 (2005) · Zbl 1065.65070 [10] Wang, C. W.; Wang, Y. J.; Xu, C. L., Aprojection method for a system of nonlinear equations with convex constraints, Math. Methods Oper. Res., 66, 33-46 (2007) [11] Bellavia, S.; Macconi, M.; Morini, B., An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 257-280 (2003) · Zbl 1018.65067 [12] Bellavia, S.; Macconi, M.; Morini, B., STRSCNE: A scaled trust-region solver for constrained nonlinear equations, Comput. Optim. Appl., 28, 31-50 (2004) · Zbl 1056.90128 [13] Bellavia, S.; Morini, B., An interior global method for nonlinear systems with simple bounds, Optim. Methods Softw., 20, 453-474 (2005) · Zbl 1134.90050 [14] Bellavia, S.; Morini, B.; Pieraccini, S., Constrained Dogleg methods for nonlinear systems with simple bounds, Comput. Optim. Appl., 53, 771-794 (2012) · Zbl 1262.90163 [15] Kanzow, C.; Klug, A., An interior-point affine-scaling trust-region method for semismooth equations with box constraints, Comput. Optim. Appl., 37, 329-353 (2007) · Zbl 1180.90219 [16] Zhao, L. J.; Sun, W. Y., A conic affine scale Dogleg method for nonlinear optimization with bound constraints, Asia Pac. J. Oper. Res., 30, 1340011 (2013), [30 pages] · Zbl 1273.90209 [17] Yu, G., A derivative-free method for solving large-scale nonlinear systems of equations, J. Ind. Manag. Optim., 6, 149-160 (2010) · Zbl 1187.65055 [19] Liu, S. Y.; Huang, Y. Y.; Jiao, H. W., Sufficient decent conjugate gradient methods for solving convex constrained nonlinear monotone equations, Abstr. Appl. Anal., 2014, 1-12 (2014) [20] Wang, C. W.; Wang, Y. J., A superlinearly convergent projection method for constrained systems of nonlinear equations, J. Global Optim., 44, 283-296 (2009) · Zbl 1191.90072 [21] Xiao, Y. H.; Zhu, H., A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing, J. Math. Anal. Appl., 405, 310-319 (2013) · Zbl 1316.90050 [22] Yu, Z. S.; Lin, J.; Sun, J.; XIao, Y. X.; Liu, L. Y.; Li, Z. H., Spectral gradient projection method for monotone nonlinear equations with convex constraints, Appl. Numer. Math., 59, 2416-2423 (2009) · Zbl 1183.65056 [23] Meintjes, K.; Morgan, A. P., A methodology for solving chemical equilibrium systems, Appl. Math. Comput., 22, 333-361 (1987) · Zbl 0616.65057 [24] Dirkse, S. P.; Ferris, M. C., MCPLIB: A collection of nonlinear mixed complementarity problems, Optim. Methods Softw., 5, 319-345 (1995) [25] Coleman, T. F.; Li, Y., On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds, Math. Program., 67, 189-224 (1994) · Zbl 0842.90106 [26] Solodov, M. V.; Svaiter, B. F., A globally convergent inexact Newton method for systems of monotone equations, (Fukushima, M.; Qi, L., Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods (1998), Kluwer Academic), 355-369 · Zbl 0928.65059 [27] Solodov, M. V.; Svaiter, B. F., A new projection method for variational inequality problems, SIAM J. Control Optim., 37, 765-776 (1999) · Zbl 0959.49007 [28] 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 [29] La Cruz, W.; Martłnez, J. M.; Raydan, M., Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comp., 75, 1429-1448 (2006) · Zbl 1122.65049 [30] Figueiredo, M. A.T.; Nowak, R., An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12, 906-916 (2003) · Zbl 1279.94015 [31] Hale, E. T.; Yin, W.; Zhang, Y., A fixed-point continuation method for $$\ell_1$$ regularized minimization with applications to compressed sensing, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076 [32] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2, 183-202 (2009) · Zbl 1175.94009 [33] Figueiredo, M. A.T.; Nowak, R.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Sign. Proces., 586-597 (2007), IEEE Press, Piscataway, NJ [34] van den Berg, E.; Friedlander, M. P., Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033 [35] Birgin, E. G.; Martínez, J. M.; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 1196-1221 (2000) · Zbl 1047.90077 [36] Xiao, Y. H.; Wang, Q. Y.; Hu, Q. J., Non-smooth equations based method for $$\ell_1$$-norm problems with applications to compressed sensing, Nonlinear Anal. TMA, 74, 3570-3577 (2011) · Zbl 1217.65069 [37] Pang, J. S., Inexact Newton methods for the nonlinear complementarity problem, Math. Program., 36, 54-71 (1986) · Zbl 0613.90097
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.