Refine
Language
- English (6)
Keywords
- TR1 Update (1)
- adjoint based updating (1)
- convergence order (1)
- local convergence (1)
- nonlinear equations (1)
- quai-Newton (1)
- quasi-Newton methods (1)
Project
- C12 (3)
Application Area
- C (3)
Automatic, or algorithmic, differentiation addresses the need for the accurate
and efficient calculation of derivative values in scientific computing. To this
end procedural programs for the evaluation of problem-specific functions are
transformed into programs that also compute the required derivative values
at the same numerical arguments in floating point arithmetic. Disregarding
many important implementation issues, we examine in this article complexity
bounds and other more mathematical aspects of the program transformation
task sketched above.
Quasi-Newton methods based on least change secant updating
formulas that solve linear equations $Ax=b$ in $n=\dim(x)=\dim(b)$ steps
can be expected to solve corresponding smooth nonlinear
systems $n$-step quadratically, i.e. with an $r$-order
of $\rho = 2^{1/n} = 1 + 1/n +O(1/n^2)$. The best rate one can
possibly expect on general problems is given by the positive root
$\rho_n$ of $\rho^n(\rho -1)=1$, for which
$\rho_n-1 = \ln(n)/n + O(1/n^2)$. To show that this upper bound is
actually achieved one usually has to impose a priori some kind of
linear independence condition on the sequence of steps taken by the
quasi-Newton iteration in question. Without any such assumptions we
establish in this paper the convergence order $\rho_n$ for the
two-sided rank one formula proposed by Schlenkrich et al in \cite{SGW06}.
It requires the evaluation of adjoint vectors, is invariant with respect
to linear transformations on the variable domain and combines the
properties of bounded deterioration and heredity.
For the solution of nonlinear equation systems
quasi-Newton methods based on low-rank updates are of particular interest. We analyze a class
of TR1 update formulas to approximate the system Jacobian. The local q-superlinear convergence for nonlinear problems is proved for a particular subclass of updates. Moreover, we give an estimate of the r-order of convergence. Numerical results comparing the TR1 method to Newton's and other quasi-Newton methods atr presented.
Adjoint Broyden a la GMRES
(2007)
It is shown here that a compact storage implementation of a quasi-Newton
method based on the adjoint Broyden update reduces in the affine
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 affine case the storage is exactly $(n+k)\cdot k$
and in the nonlinear case the same bound can be achieved if adjoints,
i.e. transposed Jacobian-vector products are available. A
transposed-free variant that relies exclusively on Jacobian-vector
products (or possibly their approximation by divided differences)
requires roughly twice the storage and turns out to be somewhat slower
in our numerical experiments reported at the end.