Adaptive Computation Methods
for Nonlinear Systems

Last Updated: 8 January 2024

Contact Information:
Leigh Tesfatsion
Professor Emerita of Economics
Courtesy Research Professor of
    Electrical & Computer Engineering
Heady Hall 260
Iowa State University
Ames, Iowa 50011-1054
https://www2.econ.iastate.edu/tesfatsi/
tesfatsi AT iastate.edu
Adaptive Homotopy Spiderweb Grid

Table of Contents:

Prelude

The following short notes summarize useful techniques for analyzing the solutions of parameterized nonlinear systems. Partitions of the solution space based on solution attributes of interest induce corresponding parameter space partitions with interesting regularities. An extreme example of this is the famous Mandelbrot Set.

Leigh Tesfatsion, Solution Analysis Techiques for General Parameterized Nonlinear Systems (Slides,173KB)

As explained in subsequent sections of this site, the solution space for parameterized nonlinear systems can further be analyzed by means of a "NASA" software program that generates the solution path corresponding to any user-specified path in the parameter space along which ill-conditioning of the solution does not arise. The program can also be used to identify regions of the parameter space where ill-conditioning arises, such as neighborhoods of singularities or bifurcation points.

Research Summary

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 adapative computation techniques are developed to facilitate the direct analysis of real-world nonlinear systems in whatever form they actually appear:

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.

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

Copyright © Leigh Tesfatsion. All Rights Reserved.