Differentiating through conjugate gradient. (2nd November 2018)

• Record Type: Journal Article
• Authors: Christianson, Bruce
• Is Part Of: Optimization methods and software. Volume 33:Number 4/6(2018)
• Page Start: 988
• Page End: 994
• Publication Date: 2018-11-02
• Subjects: Automatic differentiation -- Taylor series -- conjugate gradient; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1425862
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We show that, although the conjugate gradient (CG) algorithm has a singularity at the solution, it is possible to differentiate forward through the algorithm automatically by re-declaring all the variables as truncated Taylor series, the type of active variable widely used in automatic differentiation (AD) tools such as ADOL-C. If exact arithmetic is used, this approach gives a complete sequence of correct directional derivatives of the solution, to arbitrary order, in a single cycle of at most n iterations, where n is the number of dimensions. In the inexact case, the approach emphasizes the need for a means by which the programmer can communicate certain conditions involving derivative values directly to an AD tool.