compute the subgradient set of $\max(x,0)$ using Danskin

67 Views Asked by At

I'd like to compute the subgradient set of $f(x):=\max(x,0)$ using Danskin's theorem, similar to what is done here. We have \begin{align} f(x) = \max(x,0) = \max\{\phi(x,z): z\in Z\} \end{align} where we must choose $\phi(x,z)$ and the compact set $Z$ appropriately.

Let $\phi(x,z) = z\cdot x$ and take $Z = [{\color{red}{c}},1]$ where we start with, say, ${\color{red}{c}} = -5$. By testing $x<0$, we see that we must take $c=0$ in order for $\phi(x,z)=f(x)$ to hold. Then for the active set $Z_0(x) = \{z^*:\phi(x,z^*) = \max_{z\in Z}\phi(x,z)\},$ we have \begin{align} \partial f(x) &= \mathrm{conv} \Big\{ \frac{\partial \phi(x,z)}{\partial x} : z \in Z_0(x)\Big\}\\ &= \mathrm{conv} \{z : z\in Z_0(x)\}\\ &= \begin{cases} \{1\}, &\text{if $x>0$}\\ [0,1], &\text{if $x=0$}\\ \{0\}, &\text{if $x<0$}. \end{cases} \end{align} Is there a better way to set $c$ besides "guess and check"? Are there rules for choosing $\phi$?