Computing subgradients, a basic example.

Question

A vector $v \in \mathbb{R}^n$ is a subgradient of a convex function at $x$ if $$f(y) \geq f(x) + <v, y - x>$$ for all $y \in dom(f).$

The set of all sub gradients is known as the sub differential denoted by $\partial f (x)$

Here is the example which I am stuck with

Let $f(x) = max \{0, (x^2 - 1)/2 \}$, then $\partial f(1) = [0,1]$ and $\partial f(-1) = [-1, 0]$

I am aware that the functions inside the max function is convex, so there is better way to do this. But the method I am using, from first principles, is not leading me to the right answer.

Note

$$f(y) = \max \{ 0, (y^2 - 1)/2 \} \geq f(1) + v(y - 1) = 0 + v(y - 1)$$

Case I. Letting $0 > (y^2 - 1)/2 \iff y \in (-1, 1)$.

Case II. Letting $0 < (y^2 - 1)/2 \iff y \in (-\infty,-1) \cup (1, \infty)$

Employing case I yields the inequality

$$0 \geq v(y - 1)$$. As $y \in (-1,1)$, RHS is true for every $v \in [0, \infty)$.

Employing case II yields the inequality

$$(y^2 - 1)/2\geq v(y - 1) \implies y + 1 \geq 2v$$. As $y \in (-\infty,-1) \cup (1, \infty)$, There appears to be no unique answer for $v$ depending on the value of $y$. But we may actually throw out this case since $y \notin dom(f)$.

Answer 1

There's a slight error when you conclude that $y + 1 \geq 2v$ for all $y \in (-\infty,-1) \cup (1,\infty)$. That inequality is only valid for $y \in (1,\infty)$.

If $y \in (\infty, -1)$, then $y -1$ is negative. So when you divide through by $y-1$, you have divided by a negative number, and the direction of the inequality must change.

Being careful about this point, we conclude that \begin{equation} y + 1 \geq 2v \quad \text{for all } y \in (1,\infty) \tag{1} \end{equation} and \begin{equation} y + 1 \leq 2v \quad \text{for all } y \in (-\infty,-1). \tag{2} \end{equation} Condition (1) is equivalent to $v \leq 1$, and condition (2) is equivalent to $v \geq 0$. So (1) and (2) are satisfied when $v \in [0,1]$.

For this problem, the answer can be obtained easily just by visualizing the graph of $f$, as in this graph.

Answer 2

You can use the following formular (see on page 4 of https://see.stanford.edu/materials/lsocoee364b/01-subgradients_notes.pdf) $$ \partial f(x)=\text{co}\left(\bigcup\left\{\partial f_i(x):f_i(x)=f(x)\right\}\right), $$ where $f(x)=\max\{f_1(x),f_2(x)\}$.

Since $f_1(x)=0, f_2(x)==(x^2-1)/2$, we have $$ \partial f_1(x)=\{0\}, \quad \partial f_2(x)=\{x\} $$ For $x=1$ we have $f(1)=\max\{f_1(1),f_2(1)\}=\max\{0,0\}=0$. Hence $$ \partial f(1)=\text{co}\left(\partial f_1(1)\bigcup\partial f_2(1)\right)=[0,1]. $$ For $x=-1$ we have $f(-1)=\max\{f_1(-1),f_2(-1)\}=\max\{0,0\}=0$. Hence $$ \partial f(-1)=\text{co}\left(\partial f_1(-1)\bigcup\partial f_2(-1)\right)=[-1,0]. $$