Algorithmic construction of the subdifferential from directional derivatives (Q2413566)

Let \(f: \mathbb{R}^n\to\mathbb{R}\) be a nonsmooth function with regular subdifferential \[ \partial f(x^0)= \{v\in\mathbb{R}^n: f(x)\geq f(x^0)+ v^T(x- x^0)+ o\| x-x^0\|\}. \] If \(f\) is convex then this subdifferential is equivalent to the classical subdifferential. If \(f\) is the maximum of a finite number of smooth functions then this subdifferential is a polyhedral set. The last case is the focus of the paper. Based on the relation \[ \partial f(x^0)= \{v\in\mathbb{R}^n: v^T d\leq df(x^0; d)\,\forall d\in\mathbb{R}^n\} \] the authors provide an algorithm to reconstruct such polyhedral subdifferentials by the computation of suitable values of the associated directional derivative \(df(x^0;d)\). In any step, a new direction is created to enlarge a polyhedral inner approximation (by adding further vertices) and to decrease an outer polyhedral approximation (by intersection with the associated half space). It is shown that the algorithm terminates after a finite number of steps. In case of \(\mathbb{R}^2\) the algorithm needs about \(3n_v\) directional derivative evaluations (where \(n\) is the number of vertices of the subdifferential). In case of \(\mathbb{R}^n\) (with \(n_v\leq 3)\), the call of directional derivatives is smaller than \(5n\).