Ideally, analysis tools should adapt to the problem at hand rather than requiring the problem to be adapted to the tools.
In a series of studies with Robert Kalaba and other collaborators, gathered together in the
final section,
below, three adaptive computation techniques are developed to facilitate the direct analysis of real-world nonlinear systems in whatever form they actually appear:
- Nonlocal comparative static analysis for tracking solutions of parameterized nonlinear systems along parameter paths;
- Automatic higher-order partial derivative evaluation through forward-mode derivative arrays;
- Adaptive homotopy methods with the continuation parameter modeled as an intelligent agent moving from 0+0i to 1+0i through the complex plane along an adaptively chosen path in a spiderweb grid.
In economic theory we are often interested in understanding how the solution
vector x(b) of a parameterized system of equations F(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 = -Fx(x(b),b)-1Fb(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 a parameterized nonlinear
system F(x,b)=0 from any desired starting point b0 for the parameter vector b are as follows: the solution vector
x(b0) at b0, together with evaluations for the adjoint and determinant of the Jacobian matrix Fx(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.