Algorithmic Differentiation of Implicit Functions and
Optimal Values
Abstract
In applied optimization, an understanding of the sensitivity
of the optimal value to changes in structural parameters
is often essential. Applications include
parametric optimization,
saddle point problems,
Benders decompositions,
and multilevel optimization.
In this paper we adapt a known automatic differentiation (AD)
technique for obtaining derivatives of implicitly defined
functions for application to optimal value functions.
The formulation we develop is well suited to
the evaluation of first and second derivatives of optimal values.
The result is a method that yields large savings in
time and memory.
The savings are demonstrated by a Benders decomposition example
using both the ADOL-C and CppAD packages.
Some of the source code for these comparisons is included as an aid
in testing with other hardware and compilers,
other AD packages,
as well as future versions of ADOL-C, CppAD.
The source code also serves as an aid in the implementation
of the method for actual applications.
In addition, it demonstrates how
multiple C++ operator overloading AD packages
can be used with the same source code.
This provides motivation for the coding numerical routines
where the floating point type is a C++ template parameter.
