Sunday, May
19, 2002
Westin Harbour Castel Hotel, Toronto, Canada
Andreas Griewank,
Technical University Dresden, Germany
Uwe Naumann, University of Hertfordshire, UK
Andrea Walther, Technical University Dresden, Germany
The solutions
of nonlinear continuous optimization problems are always characterized by
neccessary conditions involving first and possibly second derivatives of objective
and constraint functions. Moreover, most deterministic optimization algorithms
for nonlinear problems are based on local Taylor expansions defined in terms
of gradients, Jacobians and Hessians. Hence the efficient provision of accurate
derivative information has always been a key concern in practical optimization.
The chainrule based technique of automatic differentiation provides first
and higher derivatives without incurring any truncation errors. The derivative
evaluation cosast can be estimated a priori as a multiple of the cost for
evaluating the undifferentiated function(s).
Software for the automatic differentiation of problem functions specified
by evaluation programs in Fortran or C has become widely available in the
last decade. As an indication of their reliability and convenience we note
that these tools have been routinely employed in the optimization server NEOS
provided by Argonne National Laboratory and Northwestern University. The possibility
to evaluate accurate sensitivities even for very complex computer models facilitates
the application of rapidly convergent optimization methods to modern parameter
estimation and design optimization problems with very many free variables.
As with all computational methodologies, an understanding of the underlying
principles allows the user to select and employ the available software tools
safely and efficiently. For large scale applications an appropriate compromise
between runtime and memory requirement should be sought.
This course will introduce the basics of AD theory and tools as well as developments
dealing with more advanced issues including differentiating iterative and
adaptive codes, evaluating higher oder derivatives, and space-time trade-offs.
The main
objective of this one day short course is to give participants a detailed
overview of AD techniques and tools. In particular, all participants will
be enabled to select appropriate modes and to estimate the cost of evaluating
all first and second derivatives that are required in various optimization
scenarios.
Examples of real-world applications will be used to illustrate the importance
of exact derivative information as part of a motivation to start off the day.
The principles behind the two basic modes of AD, i.e. the forward and reverse
modes, are introduced both from a theoretical and a more implementation-oriented
point of view.
The second part of the morning will a practical introduction to AD in the
context of source transformation tools illustrated with the aid of ADIFOR,
ADIC, and Odyssee. Several important issues specific to source transformation
will be discussed. Using some simple examples we show how exact derivative
information can be generated efficiently from an existing Fortran or C Code
using AD.
After lunch we will turn to the implementation of AD using operator overloading.
The basic ideas of this approach are explained. Then, for the same examples
as in the morning the automatic differentiation of C- and MATLAB-codes is
illustrated by applying ADOL-C and ADMAT/ADMIT. The AD packages used in the
two practical sessions were selected as a reasonably representetive sample
of the available AD tools.
In a second part of the afternoon we will discuss several possibilities for
user assistance to enhance the automatic differentiation of source codes.
For example, the detection and exploitation of sparsity and other structure
in nonlinear problems has not yet been fully automated. By employing generalizations
of the column-grouping techniques familiar from differencing one may evaluate
Jacobians with typical sparsity patterns at a small multiple of the cost of
evaluating the underlying vector function.
Furthermore, loops representing iterations or evolutions over a large number
of (pseudo-)time steps can be differentiated much more efficiently than in
a black-box fashion. Finally, methods for computing derivatives of arbitrary
order in one or more variables are explained.
We conclude the afternoon with an outlook on future projects in AD software
development and on open research questions. The integration of AD functionality
into an existing compiler environment is elaborated in some detail. A first
approach and preliminary results are presented.
Introductory 50%
Intermediate 30%
Advanced 20%
Morning
8:00 - 8:45 Introduction and Motivation
8.45 - 10.00 Basics of Automatic Differentiation
10.00 - 10.30 Coffee break
10.30 - 12.00 Automatic Differentiation by Source Transformation: ADIFOR, ADIC, and Odyssee
Afternoon
12.00 - 1:15 Lunch
1:15 - 2:45 Automatic Differentiation by Operator Overloading: ADOL-C and ADMAT/ADMIT
2:45 - 3:15 Coffee break
3:15 - 4:15 Enhancing efficiency through user assistance
4:15 - 4:45 Compiler integration and other developments
Adjourn
Background Reading
Seats are limited. We urge attendees to register in advance. To register, please complete the online Preregistration Form (available shortly) and submit to SIAM. Registration fee for the course includes course notes, coffee breaks, and lunch on Sunday, May 19.
More specific details, regarding location, will be provided soon.