directional derivative of convex function sublinear proving that fact

Question

How can we show that the directional derivative of a proper convex function on $\mathbb{R}^n$ is sublinear?

Thank you!

Answer 1

Suppose $x \in \text{dom} f$, and let $df(x,h) = \lim_{t \downarrow 0} \frac{f(x+th)-f(x)}{t}$.

To see that the limit exists (it may be $\pm \infty$), let $I_{x,h} = \{t \geq 0 | x+th \in \text{dom} f \}$. $I_{x,h}$ is convex, and $0 \in I_{x,h}$. If $I_{x,h} = \{0 \}$, then $df(x,h) = +\infty$, otherwise consider $\phi(t) = f(x+th)$ on $I_{x,h}$. Convexity of $\phi$ shows that if $0<u<v$, and $v \in I_{x,h}$, then $\frac{\phi(u)-\phi(0)}{u} \leq \frac{\phi(v)-\phi(0)}{v}$, from which it follows that $t \mapsto \frac{\phi(t)-\phi(0)}{t}$ is non-decreasing, and the existence of the (possibly extended valued) limit follows from this. It also follows from this that $df(x,h) = \inf_{t > 0} \frac{f(x+th)-f(x)}{t} = \inf_{s > 0} s (f(x+\frac{h}{s})-f(x))$.

Note that positive homogeneity follows from the definition, ie, if $\lambda \geq 0$, then $df(x,\lambda h) = \lambda df(x,h)$.

Two other facts are needed to finish:

First, suppose $g$ is convex on some domain $C$. Then the function $\eta((x,s)) = s g(\frac{x}{s})$ is convex on $C \times (0,\infty)$. This follows from (with $\lambda_k \geq 0$, $\lambda_1+\lambda_2 = 1$) \begin{eqnarray} \eta(\lambda_1 (x_1, s_1) + \lambda_2 (x_2, s_2)) &=& (\lambda_1 s_1 + \lambda_2 s_2) g (\frac{\lambda_1 x_1 + \lambda_2 x_2}{\lambda_1 s_1 + \lambda_2 s_2}) \\ & = & (\lambda_1 s_1 + \lambda_2 s_2) g (\frac{\lambda_1 s_1 }{\lambda_1 s_1 + \lambda_2 s_2} \frac{x_1}{s_1} + \frac{\lambda_2 s_2 }{\lambda_1 s_1 + \lambda_2 s_2} \frac{x_2}{s_2}) \\ & \leq & (\lambda_1 s_1 + \lambda_2 s_2) \left[ \frac{\lambda_1 s_1 }{\lambda_1 s_1 + \lambda_2 s_2} g ( \frac{x_1}{s_1}) + \frac{\lambda_2 s_2 }{\lambda_1 s_1 + \lambda_2 s_2} g(\frac{x_2}{s_2}) \right] \\ &=& \lambda_1 s_1 g ( \frac{x_1}{s_1}) + \lambda_2 s_2 g(\frac{x_2}{s_2}) \\ &=& \lambda_1 \eta((x_1,s_1)) + \lambda_2 s_2 \eta((x_2,s_2)) \end{eqnarray}

Second, suppose $\theta$ is convex on some domain $C\times D$. Then $x \mapsto \inf_{y \in D} \theta((x,y))$ is convex. To see this, let $\epsilon>0$ and choose $y_k \in D$ such that $\epsilon+\inf_{y \in D} \theta((x_k,y)) \geq \theta((x_k,y_k))$. Then

\begin{eqnarray} \inf_{y \in D} \theta(\lambda_1(x_1,y)+ \lambda_2 (x_2,y)) &\leq& \theta(\lambda_1(x_1,y_1)+ \lambda_2 (x_2,y_2)) \\ &\leq & \lambda_1 \theta((x_1,y_1)) + \lambda_2 \theta((x_2,y_2)) \\ & \leq & \lambda_1 \inf_{y \in D} \theta((x_1,y)) + \lambda_2 \inf_{y \in D} \theta((x_2,y)) + \epsilon \end{eqnarray} Since this is true for all $\epsilon >0$, the result follows.

Consider the function $h \mapsto f(x+h)-f(x)$ and apply the first result which shows that $(h,s) \mapsto s (f(x+\frac{h}{s})-f(x))$ is convex, and the second result shows that $h \mapsto \inf_{s>0} s (f(x+\frac{h}{s})-f(x))$ is convex. It follows that $h \mapsto df(x,h)$ is convex, and so $df(x,\frac{1}{2}(h_1+h_2)) \leq \frac{1}{2}(df(x,h_1)+df(x,h_2))$. Since $h \mapsto df(x,h)$ is positive homogeneous, multiplying across by $2$ yields $df(x,h_1+h_2) \le df(x,h_1)+df(x,h_2)$, hence the directional derivative is sublinear in the second argument.