The following technical report is available from http://aib.informatik.rwth-aachen.de:
Adjoint Subgradient Calculation for McCormick Relaxations Markus Beckers, Viktor Mosenkis, Michael Maier, Uwe Naumann AIB 2011-10
In [Corbett 2010] the library modMC was presented which allows the propagation of McCormick relaxations and their corresponding subgradients based on the forward mode of Algorithmic Differentiation (AD). Subgradients are natural extensions of usual derivatives which allow the application of derivative based methods on possibly nondifferentiable convex and concave functions. These subgradients can be computed by AD, a method which allows the computation of derivatives with machine accuracy even for highly complex functions implemented by a computer program. In this article we present the advancement of modMC by reverse mode AD. Reverse mode AD is an adjoint method for the propagation of derivatives which is preferable when scalar functions are considered. We describe the theory behind the application of reverse mode in subgradient propagation as well as the improved library amodMC in detail. The calculated subgradients are used in an deterministic global optimization algorithm which is based on a branch-and-bound method. The improvements gained using Reverse instead of Forward mode AD are illustrated by several examples.