I am trying to compute the subdifferential set of the convex function \begin{align} f_n(x_1,x_2,\ldots, x_n) := \max(x_1+\max(x_2 + \cdots + \max(x_n,0),0),\cdots0). \end{align} I'm considering for now the two dimensional case \begin{align} f_2(x_1,x_2) := \max(x_1 + \max(x_2,0),0) \overset{(*)}{=} \max\big\{ x_1 + \frac{x_2+|x_2|}{2},0\big\} \end{align} where $(*)$ uses the relation $2\max(a,b) = a+b+|a-b|$. Now for $g(x) = \max(x,0)$, we have \begin{align} \partial g(x) = \begin{cases} \{1\},&\text{if $x>0$}\\ \mathrm{conv}(\{1\}\cup\{0\}) = [0,1],&\text{if $x=0$}\\ \{0\},&\text{if $x<0$} \end{cases}.\tag{$**$} \end{align}
What is $\partial f_2(x_1,x_2)$? What is $\partial f(x_1,\ldots,x_n)$? Does it help to use $(**)$?
EDIT:
Here's my attempt.
- $x_1=0$, $x_2=0$: $\partial f(x) = \mathrm{conv}\big( \{(1,1)^\top\}, \{(1,0)^\top\}, \{(0,0)^\top\} \big)$
- $x_1=0$, $x_2<0$: $\partial f(x) = \mathrm{conv}\big( \{(1,0)^\top\}, \{(0,0)^\top\} \big)$
- $x_1+x_2=0$ and $x_1<0$: $\partial f(x) = \mathrm{conv}\big( \{(1,1)^\top\}, \{(0,0)^\top\} \big)$
- $x_1+x_2<0$ and $x_1<0$: $\partial f(x) = \{(0,0)^\top\}$
- $x_1>0$ and $x_2=0$: $\partial f(x) = \mathrm{conv}\big( \{(1,1)^\top\}, \{(1,0)^\top\} \big)$
- $x_1>0$ and $x_2<0$: $\partial f(x) = \{(1,0)^\top\}$
- $x_1+x_2>0$ and $x_2>0$: $\partial f(x) = \{(1,1)^\top\}$