2021
Journal article
Open Access
Solving nonlinear systems of equations via spectral residual methods: stepsize selection and applications
Meli E., Morini B., Porcelli M., Sgattoni C.
Nonlinear systems of equation Computational Mathematics Steplength selection FOS: Mathematics Nonlinear systems of equations Spectral gradient methods Approximate norm descent method Approximate norm descent methods Spectral gradient method General Engineering Computational Theory and Mathematics Mathematics - Numerical Analysis Theoretical Computer Science Numerical Analysis Optimization and Control (math.OC) Software Numerical Analysis (math.NA) Applied Mathematics Mathematics - Optimization and Control
Spectral residual methods are derivative-free and low-cost per iteration procedures for solving nonlinear systems of equations. They are generally coupled with a nonmonotone linesearch strategy and compare well with Newton-based methods for large nonlinear systems and sequences of nonlinear systems. The residual vector is used as the search direction and choosing the steplength has a crucial impact on the performance. In this work we address both theoretically and experimentally the steplength selection and provide results on a real application such as a rolling contact problem.
Source: Journal of scientific computing 90 (2021). doi:10.1007/s10915-021-01690-x
Publisher: Plenum Press,, New York , Stati Uniti d'America
[1] Awwal, A. M., Kumam, P., Abubakar, A. B., Wakili, A., Pakkaranang, N.: A new hybrid spectral gradient projection method for monotone system of nonlinear equations with convex constraints. Thai J. Math. 66-88 (2018).
[2] Barzilai, J., Borwein, J.: Two point step gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988).
[3] Birgin, E. G., Martinez, J. M., Raydan, M.: Spectral Projected Gradient Methods: review and Perspectives. J. Stat. Softw. 60(3) (2014).
[4] Bonettini, S., Zanella, R., Zanni, L.: A scaled gradient projection method for constrained image deblurring. Inverse Probl. 25(1), 015002-015002 (2009).
[5] C. Carcasci, L. Marini, B. Morini, M. Porcelli, A new modular procedure for industrial plant simulations and its reliable implementation, Energy, 94, pp. 380-390, 2016.
[6] Crisci, S., Ruggiero, V., Zanni, L.:Steplength selection in gradient projection methods for box-constrained quadratic programs. Appl. Math. Comput. 356(1), 312-327 (2019).
[7] Curtis, A.R., Powell, M.J.D., Reid, J.K.: On the estimation of sparse Jacobian matrices, IMA J. Appl. Math., 13, 117-119 (1974).
[8] Dai, Y. H., Fletcher R.:Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math. 100, 21-47 (2005)
[9] Dai, Y. H., Hager, W., W., Schittkowski, K., Zhang, H.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26(3), 604-627 (2006).
[10] De Asmundis, R., di Sera no, D., Riccio, F., Toraldo, G.: On spectral properties of steepest descent methods. IMA J. Numer. Anal. 33(4), 1416-1435 (2013).
[11] Dennis Jr., J. E., Schnabel., R. B.: Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cli s, NJ (1983).
[12] di Sera no, D., Ruggero, V., Toraldo, G., Zanni, L.: On the steplength selection in gradient methods for unconstrained optimization. Appl. Math. Comput. 318, 176-195 (2018).
[13] E.D. Dolan, J.J. More, Benchmarking optimization software with performance pro les, Mathematical Programming 91 (2002), 201-213.
[14] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, VolB v 1 1 1 e l 2 4 4 3 5 4 4 5 5 5 8 6 2 8 6 2 9 5 2 3 5 3 3 3 3 4 6 2 B le c e 1 7 5 5 0 5 6 2 0 2 2 3 6 8 3 7 4 9 5 3 0 9 9 8 8 7 2 8 m co ru B 0 0 1 4 1 4 7 0 8 2 1 9 3 8 5 0 1 5 0 4 1 7 1 2 7 1 7 4 i t y ume I. Springer Series in Operations Research, Springer, New York (2003).
[15] Fletcher, R.: On the Barzilai-Borwein method. Optimization and control with applications, Appl. Optimizat. 96, 235-256, Springer, New York (2005).
[16] Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Manag. Optim. 4(2), 299-312 (2008).
[17] Glunt, W., Hayden, T., L., Raydan, M.: Molecular conformations from distance matrices. J. Comput. Chem. 14(1), 114-120 (1993).
[18] Golub, G. H., Van Loan, C. F.: Matrix computations. Johns Hopkins Series in the Mathematical Sciences 3, Johns Hopkins University Press, Baltimore, MD (1983).
[19] Goncalves, M.L.N., Oliveira, F.R.: On the global convergence of an inexact quasi-Newton conditional gradient method for constrained nonlinear systems (2018).
[20] Grippo, L., Lampariello, S., Lucidi, S.: A nonmonotone linesearch technique for Newton's methods. SIAM J. Numer. Anal. 23, 707-716 (1986).
[21] Grippo, L., Sciandrone, M.: Nonmonotone derivative-free methods for nonlinear equations. Comput. Optim. Appl. 37, 297-328 (2007).
[22] Gu, G. Z., Li, D. H., Qi, L., Zhou, S. Z.: Descend directions of quasi-Newton methods for symmetric nonlinear equations. SIAM J. Numer. Anal. 40, 1763-1774 (2002).
[23] Kalker, J.: Three-Dimensional elastic bodies in rolling contact. Kluwer Academic Print, Delft (1990).
[24] Kalker, J., Jacobson, B,: Rolling contact phenomena. Springer Verlag, Wien (2000).
[25] La Cruz, W., Raydan, M.: Nonmonotone spectral methods for large-scale nonlinear systems. Optim. Method Softw. 18, 583-599 (2003).
[26] La Cruz, W., Martinez, J. M., Raydan, M.: Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. Math. Comput. 75, 1429-1448 (2006).
[27] La Cruz, W.: A projected derivative-free algorithm for nonlinear equations with convex constraints. Optim. Method Softw. 29, 24-41 (2014).
[28] Li, D.H., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optim. Method Softw. 13(3), 181-201 (2000).
[29] 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).
[30] Liu, J., Li, S.: Multivariate spectral dy-type projection method for convex constrained nonlinear monotone equations. J. Ind. Manag. Optim. 13, 283-295 (2017).
[31] Marini, L. , Morini, B., Porcelli, M.: Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications. Comput. Optim. Appl. 71, 147-170 (2018).
[32] Mohammad, H., Abubakar A.,B.: A positive spectral gradient-like method for large-scale nonlinear monotone equations. Bull Comput. Appl. Math. 5, 99-115 (2017).
[33] Morini, B., Porcelli, M.: TRESNEI, a Matlab trust-region solver for systems of nonlinear equalities and inequalities. Comput. Optim. Appl. 51, 27-49 (2012).
[34] Morini, B., Porcelli, M., Toint, P.: Approximate norm descent methods for constrained nonlinear systems. Math. Comput. 87, 1327-1351 (2018).
[35] Raydan, M.: Convergence properties of the Barzilai and Borwein Gradient Method. PhD Thesis, Rice University (1991).
[36] Raydan, M.: On the Barzilai and Borwein choice of step length for the gradient method. IMA J. Numer. Anal. 13, 321-326 (1993).
[37] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optimiz. 7, 26-33 (1997).
[38] Simpack Multibody Simulation Software. Dassault Systemes GmbH.
[39] Yu, Z., Lin, J., Sun, J., Xiao, Y., Liu, L., Li, Z.: Spectral gradient projection method for monotone nonlinear d e t :08 842 540 197 433 790 188 416 761 201 432 Fin 975 199 217 959 567 064 052 166 Fin 740 Fin 133 144 794 340 933 495 657 846 459 481 648 803 420 517 782 697 460 470 708 r a e 1 1 1 2 2 1 2 1 2 1 3 1 1 1 2 A :10 953 628 442 275 402 462 936 576 922 336 227 029 708 268 Fni Fin Fin Fin 427 Fin Fin Fin 468 Fin Fin Fin 607 787 Fin Fin 087 794 209 209 712 804 845 658 679 720 046 c h a 1 1 1 3 4 5 3 1 1 1 1 e = :08 663 905 261 Fin 235 234 666 Fin 262 829 Fin 139 Fin Fin 072 Fin Fin Fin 665 Fin 702 Fin 783 581 Fin Fin 366 872 Fin Fin 865 718 071 Fin 526 611 830 133 775 876 200 o f 1 1 1 4 1 2 1 2 1 1 equations with convex constraints. Appl. Numer. Math. 59, 2416-2423 (2009).
[40] Varadhan, R., Gilbert, P. D.: BB: an R package for solving a large system of nonlinear equations and for optimizing a high-dimensional nonlinear objective function. J. Stat. Softw. 32 (4) (2010).
[41] Vollebregt, E. A. H.: Re nement of Kalker's rolling contact model. Bracciali, Proceedings of the 8th International Conference on Contact Mechanics and Wear of Rail-Wheel Systems (CM2009), Firenze, 2009.
[42] Vollebregt, E. A. H.: User guide for CONTACT, Rolling and sliding contact with friction. Technical Report TR09-03, version v15.1.1 (2015).
[43] Zhang, L., Zhou, W.: Spectral gradient projection method for solving nonlinear monotone equations. J. Comput. Appl. Math. 196, 478-484 (2006).
[44] Zhou, B., Gao, L., Dai, Y. H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35(1), 69-86 (2006).
[2] Barzilai, J., Borwein, J.: Two point step gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988).
[3] Birgin, E. G., Martinez, J. M., Raydan, M.: Spectral Projected Gradient Methods: review and Perspectives. J. Stat. Softw. 60(3) (2014).
[4] Bonettini, S., Zanella, R., Zanni, L.: A scaled gradient projection method for constrained image deblurring. Inverse Probl. 25(1), 015002-015002 (2009).
[5] C. Carcasci, L. Marini, B. Morini, M. Porcelli, A new modular procedure for industrial plant simulations and its reliable implementation, Energy, 94, pp. 380-390, 2016.
[6] Crisci, S., Ruggiero, V., Zanni, L.:Steplength selection in gradient projection methods for box-constrained quadratic programs. Appl. Math. Comput. 356(1), 312-327 (2019).
[7] Curtis, A.R., Powell, M.J.D., Reid, J.K.: On the estimation of sparse Jacobian matrices, IMA J. Appl. Math., 13, 117-119 (1974).
[8] Dai, Y. H., Fletcher R.:Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math. 100, 21-47 (2005)
[9] Dai, Y. H., Hager, W., W., Schittkowski, K., Zhang, H.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26(3), 604-627 (2006).
[10] De Asmundis, R., di Sera no, D., Riccio, F., Toraldo, G.: On spectral properties of steepest descent methods. IMA J. Numer. Anal. 33(4), 1416-1435 (2013).
[11] Dennis Jr., J. E., Schnabel., R. B.: Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cli s, NJ (1983).
[12] di Sera no, D., Ruggero, V., Toraldo, G., Zanni, L.: On the steplength selection in gradient methods for unconstrained optimization. Appl. Math. Comput. 318, 176-195 (2018).
[13] E.D. Dolan, J.J. More, Benchmarking optimization software with performance pro les, Mathematical Programming 91 (2002), 201-213.
[14] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, VolB v 1 1 1 e l 2 4 4 3 5 4 4 5 5 5 8 6 2 8 6 2 9 5 2 3 5 3 3 3 3 4 6 2 B le c e 1 7 5 5 0 5 6 2 0 2 2 3 6 8 3 7 4 9 5 3 0 9 9 8 8 7 2 8 m co ru B 0 0 1 4 1 4 7 0 8 2 1 9 3 8 5 0 1 5 0 4 1 7 1 2 7 1 7 4 i t y ume I. Springer Series in Operations Research, Springer, New York (2003).
[15] Fletcher, R.: On the Barzilai-Borwein method. Optimization and control with applications, Appl. Optimizat. 96, 235-256, Springer, New York (2005).
[16] Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Manag. Optim. 4(2), 299-312 (2008).
[17] Glunt, W., Hayden, T., L., Raydan, M.: Molecular conformations from distance matrices. J. Comput. Chem. 14(1), 114-120 (1993).
[18] Golub, G. H., Van Loan, C. F.: Matrix computations. Johns Hopkins Series in the Mathematical Sciences 3, Johns Hopkins University Press, Baltimore, MD (1983).
[19] Goncalves, M.L.N., Oliveira, F.R.: On the global convergence of an inexact quasi-Newton conditional gradient method for constrained nonlinear systems (2018).
[20] Grippo, L., Lampariello, S., Lucidi, S.: A nonmonotone linesearch technique for Newton's methods. SIAM J. Numer. Anal. 23, 707-716 (1986).
[21] Grippo, L., Sciandrone, M.: Nonmonotone derivative-free methods for nonlinear equations. Comput. Optim. Appl. 37, 297-328 (2007).
[22] Gu, G. Z., Li, D. H., Qi, L., Zhou, S. Z.: Descend directions of quasi-Newton methods for symmetric nonlinear equations. SIAM J. Numer. Anal. 40, 1763-1774 (2002).
[23] Kalker, J.: Three-Dimensional elastic bodies in rolling contact. Kluwer Academic Print, Delft (1990).
[24] Kalker, J., Jacobson, B,: Rolling contact phenomena. Springer Verlag, Wien (2000).
[25] La Cruz, W., Raydan, M.: Nonmonotone spectral methods for large-scale nonlinear systems. Optim. Method Softw. 18, 583-599 (2003).
[26] La Cruz, W., Martinez, J. M., Raydan, M.: Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. Math. Comput. 75, 1429-1448 (2006).
[27] La Cruz, W.: A projected derivative-free algorithm for nonlinear equations with convex constraints. Optim. Method Softw. 29, 24-41 (2014).
[28] Li, D.H., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optim. Method Softw. 13(3), 181-201 (2000).
[29] 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).
[30] Liu, J., Li, S.: Multivariate spectral dy-type projection method for convex constrained nonlinear monotone equations. J. Ind. Manag. Optim. 13, 283-295 (2017).
[31] Marini, L. , Morini, B., Porcelli, M.: Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications. Comput. Optim. Appl. 71, 147-170 (2018).
[32] Mohammad, H., Abubakar A.,B.: A positive spectral gradient-like method for large-scale nonlinear monotone equations. Bull Comput. Appl. Math. 5, 99-115 (2017).
[33] Morini, B., Porcelli, M.: TRESNEI, a Matlab trust-region solver for systems of nonlinear equalities and inequalities. Comput. Optim. Appl. 51, 27-49 (2012).
[34] Morini, B., Porcelli, M., Toint, P.: Approximate norm descent methods for constrained nonlinear systems. Math. Comput. 87, 1327-1351 (2018).
[35] Raydan, M.: Convergence properties of the Barzilai and Borwein Gradient Method. PhD Thesis, Rice University (1991).
[36] Raydan, M.: On the Barzilai and Borwein choice of step length for the gradient method. IMA J. Numer. Anal. 13, 321-326 (1993).
[37] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optimiz. 7, 26-33 (1997).
[38] Simpack Multibody Simulation Software. Dassault Systemes GmbH.
[39] Yu, Z., Lin, J., Sun, J., Xiao, Y., Liu, L., Li, Z.: Spectral gradient projection method for monotone nonlinear d e t :08 842 540 197 433 790 188 416 761 201 432 Fin 975 199 217 959 567 064 052 166 Fin 740 Fin 133 144 794 340 933 495 657 846 459 481 648 803 420 517 782 697 460 470 708 r a e 1 1 1 2 2 1 2 1 2 1 3 1 1 1 2 A :10 953 628 442 275 402 462 936 576 922 336 227 029 708 268 Fni Fin Fin Fin 427 Fin Fin Fin 468 Fin Fin Fin 607 787 Fin Fin 087 794 209 209 712 804 845 658 679 720 046 c h a 1 1 1 3 4 5 3 1 1 1 1 e = :08 663 905 261 Fin 235 234 666 Fin 262 829 Fin 139 Fin Fin 072 Fin Fin Fin 665 Fin 702 Fin 783 581 Fin Fin 366 872 Fin Fin 865 718 071 Fin 526 611 830 133 775 876 200 o f 1 1 1 4 1 2 1 2 1 1 equations with convex constraints. Appl. Numer. Math. 59, 2416-2423 (2009).
[40] Varadhan, R., Gilbert, P. D.: BB: an R package for solving a large system of nonlinear equations and for optimizing a high-dimensional nonlinear objective function. J. Stat. Softw. 32 (4) (2010).
[41] Vollebregt, E. A. H.: Re nement of Kalker's rolling contact model. Bracciali, Proceedings of the 8th International Conference on Contact Mechanics and Wear of Rail-Wheel Systems (CM2009), Firenze, 2009.
[42] Vollebregt, E. A. H.: User guide for CONTACT, Rolling and sliding contact with friction. Technical Report TR09-03, version v15.1.1 (2015).
[43] Zhang, L., Zhou, W.: Spectral gradient projection method for solving nonlinear monotone equations. J. Comput. Appl. Math. 196, 478-484 (2006).
[44] Zhou, B., Gao, L., Dai, Y. H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35(1), 69-86 (2006).
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:468675,
title = {Solving nonlinear systems of equations via spectral residual methods: stepsize selection and applications},
author = {Meli E. and Morini B. and Porcelli M. and Sgattoni C.},
publisher = {Plenum Press,, New York , Stati Uniti d'America},
doi = {10.1007/s10915-021-01690-x and 10.48550/arxiv.2005.05851},
journal = {Journal of scientific computing},
volume = {90},
year = {2021}
}
0000-0003-0183-1204
