Directional derivate of a convex proper function

Question

The subgradient at $x\in\mathbb{R}^n$ of a convex function $f:\mathbb{R}^n\to\mathbb{R}$ is any vector $g\in \mathbb{R}^n$ such that $$f(y)\geq f(x) + g^T(y-x) \qquad\forall y \in \mathbb{R}^n.$$I have some problem about showing that $$\frac{\partial f}{\partial d}:=lim_{t\to0}\frac{f(x+td)-f(x)}{t}=max\{g^Td\,|\,g\, \text{is a subgradient}\}$$

Answer 1

When you refer to a subgradient, you should say at which point otherwise it doesn't make sense. Thus, all "subgradient" instances in your question should be replaced by "subgradient at $x$".

Let me use the standard notation $f'(x; d)$ to denote the directional derivative of $f$ at $x$ in direction $d$: \begin{equation} f'(x; d) = \lim_{t\to 0^+} \frac{f(x+td) - f(x)}{t}. \end{equation} We need to prove that \begin{equation} f'(x; d) = \max_{g\in \partial f(x)} g^T d \quad\forall x,d\in\mathbb{R^n}. \end{equation} This is a standard result in convex analysis and proofs can be found in any books on the topic. My proof below may be slightly different than those, in which I explicitly provide the subset of maximum solutions.

First, notice that \begin{equation} f(x+td) - f(x) \ge g^T(x+td-x) = tg^Td \quad \forall g\in\partial f(x), \forall x,d,t, \end{equation} we obtain \begin{equation} \boxed{f'(x; d) \ge g^T d \quad\forall g\in\partial f(x),\forall x,d.}\tag{*} \end{equation} We can prove the reverse inequality, or alternatively show that there exists $g\in\partial f(x)$ such that equality holds. To this end, we need some fundamental properties of directional derivatives:

1. $f(y) \ge f(x) + f'(x;y-x) \quad\forall x,y$.

2. The function $h(u) = f'(x;u)$ is convex and homogeneous of degree 1.

Both can be proved easily using the definition of $f(x;u)$ and the convexity of $f$.

Since $h(u)$ is convex, we have $h(u)\neq\emptyset$ and thus $$h(v) - h(u) \ge g^T(v-u)\quad \forall v,\forall g\in\partial h(u).$$ If we choose $v=tu$ for some $t$, then $h(v) = h(tu) = th(u)$ and we obtain $$(t-1)h(u) \ge (t-1)g^Tu.$$ Because the above holds for any $t$, we must have $h(u) = g^Tu$. Hence, we have proved that \begin{equation} \boxed{h(u) = g^Tu \quad\forall g\in\partial h(u), \forall u.}\tag{**} \end{equation} Using this equality and the above first property of directional derivatives, we get $$f(y) \ge f(x) + f'(x;y-x) = f(x) + h(y-x) = f(x) + g^T(y-x) \quad \forall g\in\partial h(y-x), \forall y,$$ which implies $\partial h(y-x) \subset \partial f(x)\ \forall y$, or equivalently $\partial h(u) \subset \partial f(x)\ \forall u$. Therefore, we see that in $(*)$, equality occurs for any $g$ in the nonempty subset $\partial h(d)$ of $\partial f(x)$. QED