Beyond Newton: Robust Methods For Solving Large Nonlinear Models In Troll
Newton's Method is an important algorithm for solving nonlinear systems of equations. For any solution algorithm, the principle concerns are robustness (finding a solution reliably) and efficiency (finding a solution quickly). Newton is simple in principle, but a useful implementation must deal with a variety of practical and theoretical obstacles.By using partial derivatives, Newton's Method can model the shape of the residual surface to provide quadratic convergence near the solution: the number of correct digits doubles each iteration. But far from the solution, the full Newton step may go too far, leading to divergence or oscillation. Or the full step may be illegal, leading to economic nonsense like negative prices and numerical problems like taking the log of a negative number. Automatic damping -- taking shorter steps along the Newton direction -- can improve global convergence in such cases.The most expensive part of Newton's Method is factoring the Jacobian matrix. The Jacobian can be very large in contemporary macroeconometric models, particularly forward-looking models that introduce simultaneity across time periods as well as between equations. Newton is impractical for such large models unless it can exploit the sparsity of the Jacobian. Sparse direct methods can be applied to the entire Jacobian; one advantage of direct methods is that after the first iteration, subsequent factorings can be extremely fast. An alternative is iterative Krylov subspace methods; their small memory requirements are an advantage, but they may fail to converge. In the case of forward-looking models, the stacked Jacobian has a block band-diagonal structure that can be exploited by direct methods or for preconditioning iterative methods.his paper describes enhancements to Newton's Method used in the TROLL modeling system and illustrates them with a variety of contemporary models.
|Date of creation:||05 Jul 2000|
|Date of revision:|
|Contact details of provider:|| Postal: |
Fax: +34 93 542 17 46
Web page: http://enginy.upf.es/SCE/Email:
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Juillard, Michel & Laxton, Douglas & McAdam, Peter & Pioro, Hope, 1998. "An algorithm competition: First-order iterations versus Newton-based techniques," Journal of Economic Dynamics and Control, Elsevier, vol. 22(8-9), pages 1291-1318, August.
- Juillard, Michel, 1996. "Dynare : a program for the resolution and simulation of dynamic models with forward variables through the use of a relaxation algorithm," CEPREMAP Working Papers (Couverture Orange) 9602, CEPREMAP.
- Hamid Faruqee & Douglas Laxton & Bart Turtelboom & Peter Isard & Eswar Prasad, 1998. "Multimod Mark III; The Core Dynamic and Steady State Model," IMF Occasional Papers 164, International Monetary Fund.
- Boucekkine, Raouf, 1995. "An alternative methodology for solving nonlinear forward-looking models," Journal of Economic Dynamics and Control, Elsevier, vol. 19(4), pages 711-734, May.
- Coletti, D. & Hunt, B. & Rose, D. & Tetlow, R., 1996. "The Bank of Canada's New Quarterly Projection Model. Part 3 , the Dynamic Model : QPM," Technical Reports 75, Bank of Canada.
When requesting a correction, please mention this item's handle: RePEc:sce:scecf0:308. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Christopher F. Baum)
If references are entirely missing, you can add them using this form.