Andreas Griewank, Humboldt University Berlin
Abstract:
It is shown that a compact storage implementation of a quasi-Newton
method based on the adjoint Broyden update reduces in the linear
case exactly to the well established GMRES procedure. Generally,
storage and linear algebra effort per step are small multiples of $n\cdot k$,
where $n$ is the number of variables and $k$ the number of steps
taken in the current cycle. In the linear case the storage is exactly
$(n+k)\cdot k$ and in the nonlinear case the same bound can be
achieved by a transposed-free variant that relies exclusively on
Jacobian-vector products. These can be evaluated in the forward mode of
automatic differentiation, or possibly approximated by a divided
difference. The exact adjoint Broyden method relies on
the reverse mode to evaluate transposed Jacobian-vector products
at a cost comparable to that of evaluating the vector-function whose
roots are to be computed.
(Joint work with Sebastian Schlenkrich und Andrea Walther.)