Can somebody explain how to find sub-gradient of $\vert x\vert^{\frac{1}{2}}$? Also, can we have sub-gradient of a non-convex function? An example would be helpful.
I am actually new to sub-gradients and trying to figure out the underlying concept. I know for a normal function like $\vert x\vert$, how to calculate it's sub-gradient. As per my understanding, a sub-gradient, $g$ exists if $f(z) \geq f(x) + g^T(z-x)$ which is applicable even for non-differentiable functions $f$.
According to me I am getting the condition $g \leq \frac{\vert z\vert^{\frac{1}{2}}}{z}$ which states that $g$ lies between infinity and -infinity. So, do we see sub-gradient exists for such a function? I am really confused with the concept of sub-gradient.
A key thing to know about the subgradient of a function $f \colon \mathbb R \to \mathbb R$ is that if $f$ is differentiable at $x_0 \in \mathbb R$, then $(\partial f)(x_0) = \{ f'(x_0)\}$, that is, the subgradient of $f$ at $x_0$ is a singleton, whose element is the derivative of $f$ at $x_0$.
Hence for all $x \ne 0$ (the points where $f$ is differentiable) we have $$(\partial f)(x) = \left\{ \frac{\text{d}}{\text{d} x} | x |^{\frac{1}{2}} \right\} = \left\{ \frac{\text{sign}(x)}{2 \sqrt{x}} \right\}.$$ To calculate the subgradient at $x = 0$ we use the definition you gave: for $y \in \mathbb R$ we have $$ y \in (\partial f)(0) \iff f(z) \ge f(0) + y \cdot (z - 0) \qquad \forall z \in \mathbb{R}. $$ For $f(x) = \sqrt{ | x |}$ this thus becomes $$ y \in (\partial f)(0) \iff \sqrt{| z |} \ge y \cdot z \qquad \forall z \in \mathbb{R}. $$ This is clearly true for $z = 0$, so we can equivalently require that $$ y \in (\partial f)(0) \iff \sqrt{| z |} \ge y \cdot z \qquad \forall z \in \mathbb{R} \setminus \{ 0 \}. $$ Depending on the sign of $z$, this can now be rearranged to \begin{equation} \begin{cases} y \le \frac{\sqrt{z}}{z} = \frac{1}{\sqrt{z}}, & \text{if } z > 0, \\ y \ge \frac{\sqrt{-z}}{z} = - \frac{1}{\sqrt{z}}, & \text{if } z < 0. \end{cases} \end{equation} The function $(0, \infty) \to (0, \infty)$, $z \mapsto \frac{1}{\sqrt{z}}$ is bijective, so the first case implies that $y \le 0$. Analogously, the second case implies $y \ge 0$. In summary we have $\partial f(0) = \{ 0 \}$.