Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions. (2nd November 2018)

• Record Type: Journal Article
• Authors: Khan, Kamil A.
• Is Part Of: Optimization methods and software. Volume 33:Number 4/6(2018)
• Page Start: 1127
• Page End: 1155
• Publication Date: 2018-11-02
• Subjects: vector forward AD mode -- nonsmooth functions -- sensitivity analysis -- generalized derivatives -- implicit functions; 90C56 -- 49J52 -- 49M15 -- 65K15; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1341506
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : A recent nonsmooth vector forward mode of algorithmic differentiation (AD) computes Nesterov's L-derivatives for nonsmooth composite functions; these L-derivatives provide useful sensitivity information to methods for nonsmooth optimization and equation solving. The established reverse AD mode evaluates gradients efficiently for smooth functions, but it does not extend directly to nonsmooth functions. Thus, this article examines branch-locking strategies to harness the benefits of smooth AD techniques even in the nonsmooth case, in order to improve the computational performance of the nonsmooth vector forward AD mode. In these strategies, each nonsmooth elemental function in the original composition is 'locked' into an appropriate linear 'branch'. The original composition is thereby replaced with a smooth variant, which may be subjected to efficient AD techniques for smooth functions such as the reverse AD mode. In order to choose the correct linear branches, we use inexpensive probing steps to ascertain the composite function's local behaviour. A simple implementation in is described, and the developed techniques are extended to nonsmooth local implicit functions and inverse functions.