Super convergence sensitivities for fixed point iteration
by
Vittorio Selmin
Alenia Torino
Coauthors: Christele Faure, INRIA Sophia Antipolis, Andreas Griewank, Technical University Dresden

In design optimization and parameter identification, objective function(s) and independent variables are typically linked through equality constraints, which we will refer to as state equations. Our key assumption is that it is impossible to form and factor the corresponding constraint Jacobian, but one has instead some fixed point algorithm for computing a feasible state given any reasonable value of the independent variables. Provided this iteration is eventually contractive we will show that and how the reduced gradient (or in other words the total derivative) of the objective with respect to the independent variables can be obtained via algorithmic differentiation (AD).

By a combination of the so-called forward and reverse mode of AD one obtains iterative approximations to the reduced gradient that converge twice as fast as the estimates computed on the basis of either alone. If there are several objectives or soft constraints one obtains a reduced Jacobian with the same superconvergence properties. The actual application of the reverse or adjoint mode is local to each iteration step, so that the memory requirement is typically not unduly enlarged.

At the end of the iteration one has also approximations to the Lagrange multipliers from the reverse mode and to the feasible tangent space from the forward mode. These quantities allow the calculation of the one-sided projection of the reduced Hessian (or second order tensor) at roughly the same cost as the reduced gradient (or Jacobian). If there are also inequality constraints our analysis applies locally, once all active constraints have been identified.

Our approach is verified by test calculations on an aircraft wing with the objective being the drag coefficients (lift is constraint) and the angle of attack as well as the number of Mach forming a 2-vector of independent variables. The state is a two-dimensional flow field defined as solution of the discretized Navier Stokes equation. From the original source code, we have isolated one step function of the solver followed by the computation of the residual in a sub-program.

We have applied the direct and reverse mode of AD (using Odyssée) to this sub-program and combine both generated sub-programs within a new step function. In this piece of code, there is no need for storing the state even though the reverse mode is applied. The sensitivity resulting from this combination is more accurate than the pure direct or reverse sensitivities. We have drawn the pure sensitivities computed in direct and reverse mode all along the solver iteration as well as the combination of both. As proven theoretically, one can see that the convergency of the sensititities is two times quicker using the combination than the pure sensitivities.

http://homepages.feis.herts.ac.uk/~comqun/AD2000/Ext_Abstracts/selmin.ps

Date received: December 31, 1999