Abstract
In this paper, we present two partitioned quasi-Newton methods for solving partially separable nonlinear equations. When the Jacobian is not available, we propose a partitioned Broyden’s rank one method and show that the full step partitioned Broyden’s rank one method is locally and superlinearly convergent. By using a well-defined derivative-free line search, we globalize the method and establish its global and superlinear convergence. In the case where the Jacobian is available, we propose a partitioned adjoint Broyden method and show its global and superlinear convergence. We also present some preliminary numerical results. The results show that the two partitioned quasi-Newton methods are effective and competitive for solving large-scale partially separable nonlinear equations.
Similar content being viewed by others
References
Bidabadi, N., Mahdavi-Amiri, N.: Superlinearly convergent exact penalty methods with projected structured secant updates for constrained nonlinear least squares. J. Optim. Theory Appl. 162, 154–190 (2014)
Bogle, I.D.L., Perkins, J.D.: A new sparsity preserving quasi-Newton update for solving nonlinear equations. SIAM J. Sci. Stat. Comput. 11, 621–630 (1990)
Broyden, C.G.: A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19, 577–593 (1965)
Broyden, C.G.: The convergence of an algorithm for solving sparse nonlinear systems. Math. Comput. 25, 285–294 (1971)
Broyden, C.G., Dennis, J.E., Moré, J.J.: On the local and superlinear convergence of quasi-Newton methods. IMA J. Appl. Math. 12, 223–245 (1973)
Dai, Y.H., Yamashita, N.: Convergence of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numer. Algebra Control Optim. 1, 61–69 (2011)
Dai, Y.H., Yamashita, N.: Analysis of sparse quasi-Newton updates with positive definite matrix completion. J. Oper. Res. Soc. Chin. 2, 39–56 (2014)
Dennis, J.E., Martínez, H.J., Tapia, R.A.: Convergence theory for the structured BFGS secant method with an application to nonlinear least squares. J. Optim. Theory Appl. 61, 161–178 (1989)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Fletcher, R., Xu, C.: Hybrid methods for nonlinear least squares. IMA J. Numer. Anal. 7, 371–389 (1987)
Fletcher, R.: An optimal positive definite update for sparse Hessian matrices. SIAM J. Optim. 5, 192–218 (1995)
Griewank, A., Toint, P.L.: Partitioned variable metric updates for large structured optimization problems. Numer. Math. 39, 119–137 (1982)
Griewank, A., Toint, P.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39, 429–448 (1982)
Griewank, A.: The “global” convergence of Broyden-like methods with a suitable line search. J. Aust. Math. Soc. Ser. B Appl. Math. 28, 75–92 (1986)
Griewank, A.: The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients. Math. Program. 50, 141–175 (1991)
Griewank, A., Walther, A.: On constrained optimization by adjoint based quasi-Newton methods. Optim. Method. Softw. 17, 869–889 (2002)
La Cruz, W., Martnez, J.M., Raydan, M.: Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. Math. Comput. 75, 1429–1448 (2006)
Lam, B.: On the convergence of a quasi-Newton method for sparse nonlinear systems. Math. Comput. 32, 447–451 (1978)
Li, D.H., Fukushima, M.: A globally and superlinearly convergent Gauss–Newton based BFGS method for symmetric nonlinear equations. SIAM J. Numer. Anal. 37, 152–172 (1999)
Li, D.H., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optim. Method. Softw. 13, 181–201 (2000)
Li, D.H., Cheng, W.Y.: Recent progress in the global convergence of quasi-Newton methods for nonlinear equations. Hokkaido Math. J. 36, 729–743 (2007)
Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989)
Mahdavi-Amiri, N., Ansari, M.R.: Superlinearly convergent exact penalty projected structured Hessian updating schemes for constrained nonlinear least squares: global analysis. Optimization 62, 675–691 (2013)
Marwil, E.: Convergence result for Schubert’s method for solving sparse nonlinear equations. SIAM J. Numer. Anal. 16, 588–604 (1979)
Schlenkrich, S., Walther, A.: Adjoint-based quasi-Newton methods for partially separable problems. PAMM 7, 2020091–2020092 (2007)
Schlenkrich, S., Walther, A.: Global convergence of quasi-Newton methods based on adjoint Broyden updates. Appl. Numer. Math. 59, 1120–1136 (2009)
Schlenkrich, S., Griewank, A., Walther, A.: On the local convergence of adjoint Broyden methods. Math. Program. 121, 221–247 (2010)
Schubert, L.K.: Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian. Math. Comput. 24, 27–30 (1970)
Toint, P.L.: On sparse and symmetric matrix updating subject to a linear equation. Math. Comput. 31, 954–961 (1977)
Toint, P.L.: Global convergence of the partitioned BFGS algorithm for convex partially separable optimization. Math. Program. 36, 290–306 (1986)
Toint, P.L.: Numerical solution of large sets of algebraic nonlinear equations. Math. Comput. 46, 175–189 (1986)
Van de Rotten, B., Lunel, S.M.V.: A limited memory Broyden method to solve high-dimensional systems of nonlinear equations. University of Leiden, Mathematical Institute, Leiden (2003)
Wang, F., Li, D.H., Qi, L.: Global convergence of Gauss–Newton-MBFGS method for solving the nonlinear least squares problem. Adv. Model. Optim. 12, 1–19 (2010)
Yabe, H., Ogasawara, H.: Quadratic and superlinear convergence of the Huschens method for nonlinear least squares problems. Comput. Optim. Appl. 10, 79–103 (1998)
Yamashita, N.: Sparse quasi-Newton updates with positive definite matrix completion. Math. Program. 115, 1–30 (2008)
Yuan, Y.X.: Recent advances in numerical methods for nonlinear equatios and nonlinear least squares. Numer. Albegra. 1, 15–34 (2011)
Acknowledgments
The work was supported by the National Natural Science Foundation of China through Grants 11371154 and 61502159. The authors would like to thank the associate editor and the two anonymous referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Cao, HP., Li, DH. Partitioned quasi-Newton methods for sparse nonlinear equations. Comput Optim Appl 66, 481–505 (2017). https://doi.org/10.1007/s10589-016-9878-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-016-9878-1
Keywords
- Partially separable nonlinear equation
- Partitioned Broyden’s rank one method
- Partitioned adjoint Broyden method
- Global convergence
- Superlinear convergence