Adaptive Computation Methods
for Nonlinear Systems

Last Updated: 2 January 2008

Site Maintained By:
Leigh Tesfatsion
Department of Economics
Iowa State University
Ames, IA 50011-1070
Tel: (515) 294-0138
FAX: (515) 294-0221
http://www.econ.iastate.edu/tesfatsi/
tesfatsi AT iastate.edu

Table of Contents:

Research Summary

In economics, as in many other disciplines, linear models have been extensively used to provide analytically tractable representations for a wide variety of processes. However, economists working with economic models based on microfoundations are continually confronted with significant nonlinearities arising from preference and production relations.

In a series of studies with Robert Kalaba and other collaborators, gathered together in the final section, below, three new techniques are developed to facilitate the analysis of nonlinear systems:

In economic theory we are often interested in understanding how the solution vector x(b) of a parameterized system of equations H(x,b)=0 varies as the parameter vector b ranges over some interval of interest. The well-known fundamental differential equation of comparative statics,
dx(b)/db = -Hx(x(b),b)-1Hb(x(b),b),
can be used to determine the nature of the change in the solution vector x(b) at a particular value b0 for the parameter vector b. However, this fundamental differential equation is analytically incomplete.

More precisely, the integration of this fundamental differential equation from initial conditions over a parameter interval would typically require the additional algebraic determination of the Jacobian inverse at each step in the integration process. For this reason many economists interpret the fundamental differential equation as a purely algebraic relation that can be used to qualitatively sign the change in the solution at the particular parameter value. Numerical integration using specific functional forms is generally not attempted.

In Kalaba and Tesfatsion (1981) the fundamental differential equation is completed by incorporating ordinary differential equations for the Jacobian inverse. As illustrated for optimal growth and taxation problems in Kalaba, Tesfatsion, and Wang (1981), this analytically complete system of ordinary differential equations can be used to track solutions for systems of parameterized nonlinear equations over parameter intervals. Thus, this complete differential system facilitates the nonlocal comparative static analysis of economic systems.

For equilibrium and optimal growth studies, it is often important to be able to determine the stability and definiteness properties of parameterized Jacobian matrices. These properties can be determined from a knowledge of the eigenvalues of the Jacobian matrix. The complete differential system developed in Kalaba and Tesfatsion (1981) for the nonlocal sensitivity analysis of general nonlinear systems turns out to be useful, as well, for the sensitivity study of parameterized matrices and their associated systems of eigenvalues and eigenvectors.

Specifically, in Kalaba, Spingarn, and Tesfatsion (1981a) it is shown how the eigenvalues and the right and left eigenvectors of a general parameterized matrix can be tracked over parameter intervals by integrating an analytically complete differential system from initial conditions. In Kalaba, Spingarn, and Tesfatsion (1981b) an analogous complete differential system is developed for tracking a single eigenvalue of a parameterized matrix together with one of its corresponding right or left eigenvectors. Finally, in Kalaba, Spingarn, and Tesfatsion (1980) it is shown show how the latter system can be used, in particular, to obtain the largest eigenvalue (Frobenius-Perron root) for any positive square matrix, an important problem arising (e.g.) in the study of Leontief input-output systems.

In the course of implementing the complete differential system developed in Kalaba and Tesfatsion (1981) in various applications, it became clear that an automatic method was needed for evaluating higher-order partial derivatives in order to make the approach practical. In Kalaba, Tesfatsion, and Wang (1983) an algorithm FEED (Fast Efficient Evaluation of Derivatives) is developed for the automatic evaluation of higher-order partial derivatives exact up to round-off and truncation error. FEED overcomes several key difficulties with previously developed automatic differentiation techniques by using forward-mode evaluation based on derivative arrays. Further potentially useful extensions of FEED are developed in Kalaba and Tesfatsion (1986b) and in Kalaba, Plum, and Tesfatsion (1987).

The initial conditions needed to integrate the complete differential system developed in Kalaba and Tesfatsion (1981) for parameterized nonlinear systems H(x,b)=0 are as follows: Starting from an initial value b0 for the parameter vector b, one needs a solution vector x(b0) together with evaluations for the adjoint and determinant of the Jacobian matrix Hx(x(b),b)) at (x(b0),b0). For many nonlinear problems, finding these needed initial values is a difficult matter in and of itself.

In Kalaba and Tesfatsion (1991) an adaptive homotopy is developed for solving nonlinear systems of equations F(x)=0 that adapts to whatever physical problem is at hand. The key new idea is the replacement of the standard homotopy continuation parameter moving from 0 to 1 along the real line with a "smart agent" able to adaptively determine a solution path from 0+0i to 1+0i in the complex plane using multi-criteria optimization. Specifically, the agent sequentially traces out a path from 0+0i to 1+0i in accordance with the following two criteria: (a) efficiency (take as few steps as possible); and (b) accuracy (avoid regions where calculations become ill-conditioned). It is therefore not necessary for the user of the homotopy to know in advance the location of folds and bifurcation points; the continuation agent applies local step-by-step testing to efficiently track around such regions in the complex plane.

Finally, in Kalaba and Tesfatsion (1990) a Fortran program NASA (Nonlocal Automated Sensitivity Analysis) is developed for solving the complete differential system in Kalaba and Tesfatsion (1981) that knits together all of these various parts. The NASA program incorporates the FEED algorithm developed in Kalaba, Tesfatsion, and Wang (1983) for the automatic evaluation of higher-order partial derivatives. The NASA program also incorporates the adaptive homotopy developed in Kalaba and Tesfatsion (1991) as the means for obtaining all required initial conditions.

The next section explains where the Fortran source code for the NASA program can be downloaded as free open-source software. All of the work summarized above is explained at some length in the articles listed in the final section.

NOTE: It is with immense sadness I report that Robert E. Kalaba, a great scholar, mentor, colleague, and friend, died on September 29, 2004.

Software and Manual Availability

Research Publications

Nonlocal Automated Sensitivity Analysis (NASA):
Tracking of Solutions for General Parameterized Nonlinear systems

Tracking of Eigenvalues and Eigenvectors for General Parameterized Matrices

Adaptive Homotopy Continuation

"Analysis does not owe its really significant increases of the last century to any mysterious use of the (imaginary number i) but to the quite natural circumstance that one has infinitely more freedom of mathematical movement if he lets quantities vary in a plane instead of only on a line." --- Leopold Kronecker.

Automatic Evaluation of Higher-Order Partial Derivatives