9.15. Directional Derivatives

This section deals with the subject of directional derivatives for convex functions.

9.15.1. Convex Real Functions

For real functions $f:\mathbb{R}\to \mathbb{R}$, several useful results are available.

Remark 9.13 (Domain of a convex real function)

The domain of a convex real function is an interval.

Let $f:\mathbb{R}\to \mathbb{R}$ be convex. Then $\mathrm{dom}f$ is convex. But every convex subset of real line is an interval.

1. Now let $I=\mathrm{dom}f$ be an interval.

2. We say $a=infI$ as the left end point of $I$.

3. We say $b=supI$ as the right end point of $I$.

4. $a$ and $b$ may or may not belong to $I$.

5. If both $a$ and $b$ belong to $I$, then $I$ is a closed interval.

6. If neither $a$ nor $b$ belongs to $I$, then $I$ is an open interval.

9.15.1.1. Characterization

Theorem 9.199 (Characterization of real convex functions)

Let $f:\mathbb{R}\to \mathbb{R}$ be a real function with $\mathrm{dom}f=I$ which is an interval (closed or open or semi-open). Let $a$ and $b$ be the left and right endpoints of the interval $I$.

The following are equivalent.

1. $f$ is convex over $I$.

2. For every $x_1,x_2,x_3\in I$ with $x_1<x_2<x_3$,

   $$\frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}.$$

3. For every $x_1,x_2,x_3\in I$ with $x_1<x_2<x_3$,

   $$\frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_2)}{x_3-x_2}.$$

4. For every $x_1,x_2,x_3\in I$ with $x_1<x_2<x_3$,

   $$\frac{f(x_3)-f(x_1)}{x_3-x_1}\le \frac{f(x_3)-f(x_2)}{x_3-x_2}.$$

Proof. (1) $⟹$ (2) Assume that $f$ is convex.

1. Let

   $$\alpha =\frac{x_3-x_2}{x_3-x_1},\beta =\frac{x_2-x_1}{x_3-x_1}.$$

2. Then, $\alpha +\beta =1$ and $\alpha ,\beta \in (0,1)$.

3. Also, verify that

   $$x_2=\alpha x_1+\beta x_3.$$

4. Thus,

   $$\begin{array}{rl}& f(x_2)\le \alpha f(x_1)+\beta f(x_3)\\ & ⟺f(x_2)\le \frac{x_3-x_2}{x_3-x_1}f(x_1)+\frac{x_2-x_1}{x_3-x_1}f(x_3)\\ & ⟺(x_3-x_1)f(x_2)\le (x_3-x_2)f(x_1)+(x_2-x_1)f(x_3)\\ & ⟺(x_3-x_1)f(x_2)\le ((x_3-x_1)-(x_2-x_1))f(x_1)+(x_2-x_1)f(x_3)\\ & ⟺(x_3-x_1)(f(x_2)-f(x_1))\le (x_2-x_1)(f(x_3)-f(x_1))\\ & ⟺\frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}.\end{array}$$

(2) $⟹$ (1)

1. Let $x_1,x_3\in I$ and $t\in (0,1)$.

2. WLOG, assume that $x_1<x_3$.

3. Let $\alpha =t$ and $\beta =(1-t)$.

4. Let $x_2=\alpha x_1+\beta x_3$.

5. Then, $x_1<x_2<x_3$.

6. From the hypothesis, we have

   $$\frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}.$$

7. Using the previous argument backwards, this implies

   $$f(x_2)\le \alpha f(x_1)+\beta f(x_3)=tf(x_1)+(1-t)f(x_3).$$

8. Thus, $f$ is convex.

(2) $⟺$ (3)

1. Pick any $x_1,x_2,x_3\in I$ with $x_1<x_2<x_3$.

2. By hypothesis (2)

   $$\begin{array}{rl}& \frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}\\ ⟺& (x_3-x_1)(f(x_2)-f(x_1))\le (x_2-x_1)(f(x_3)-f(x_1))\\ ⟺& (x_3-x_1)f(x_2)\le ((x_3-x_1)-(x_2-x_1))f(x_1)+(x_2-x_1)f(x_3)\\ ⟺& ((x_3-x_2)+(x_2-x_1))f(x_2)\le ((x_3-x_2)f(x_1)+(x_2-x_1)f(x_3)\\ ⟺& (x_3-x_2)(f(x_2)-f(x_1))\le (x_2-x_1)(f(x_3)-f(x_2))\\ ⟺& \frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_2)}{x_3-x_2}.\end{array}$$

(2) $⟺$ (4)

1. Pick any $x_1,x_2,x_3\in I$ with $x_1<x_2<x_3$.

2. By hypothesis (2)

   $$\begin{array}{rl}& \frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}\\ ⟺& (x_3-x_1)(f(x_2)-f(x_1))\le (x_2-x_1)(f(x_3)-f(x_1))\\ ⟺& (x_3-x_1)f(x_2)\le (x_3-x_2)f(x_1)+((x_2-x_3)+(x_3-x_1))f(x_3)\\ ⟺& (x_3-x_1)(f(x_2)-f(x_3))\le (x_3-x_2)(f(x_1)-f(x_3))\\ ⟺& (x_3-x_1)(f(x_3)-f(x_2))\ge (x_3-x_2)(f(x_3)-f(x_1))\\ ⟺& (x_3-x_2)(f(x_3)-f(x_1))\le (x_3-x_1)(f(x_3)-f(x_2))\\ ⟺& \frac{f(x_3)-f(x_1)}{x_3-x_1}\le \frac{f(x_3)-f(x_2)}{x_3-x_2}.\end{array}$$

9.15.1.2. One Sided Derivatives

Recall from Definition 2.83 that if $f$ is defined over $[a,b)$, then the right hand derivative is defined as:

$$f_{+}^{\prime }(a)=\underset{x\to a^{+}}{lim}\frac{f(x)-f(a)}{x-a}=\underset{h\downarrow 0}{lim}\frac{f(a+h)-f(a)}{h}$$

if the limit exists. Similarly, if $f$ is defined over $(c,a]$, then the left hand derivative is defined as:

$$f_{-}^{\prime }(a)=\underset{x\to a^{-}}{lim}\frac{f(x)-f(a)}{x-a}=\underset{h\uparrow 0}{lim}\frac{f(a+h)-f(a)}{h}=\underset{r\downarrow 0}{lim}\frac{f(a)-f(a-r)}{r}$$

if the limit exists.

We introduce two helper functions

$$s_{+}(x,h)=\frac{f(x+h)-f(x)}{h}$$

and

$$s_{-}(x,h)=\frac{f(x)-f(x-h)}{h}$$

where $h>0$.

Then

$$f_{+}^{\prime }(x)=\underset{h\downarrow 0}{lim}{s}_{+}(x,h)$$

and

$$f_{-}^{\prime }(x)=\underset{h\downarrow 0}{lim}{s}_{-}(x,h).$$

An interesting property of convex functions is that the one sided derivatives always exist. On the real line, there are only two directions to move; left and right. The one sided derivatives play the role of directional derivatives on the real line.

Lemma 9.4 (Monotonicity of $s_{+}$ and $s_{-}$ for convex functions)

Let $f:\mathbb{R}\to \mathbb{R}$ with $\mathrm{dom}f=I$ be convex. Let $a$ and $b$ be the left and right endpoints of the interval $I$. Then $s_{+}$ and $s_{-}$ as functions of $h$ are monotonic.

1. $s_{+}(x,h)$ is a nondecreasing function of $h$.

2. $s_{-}(x,h)$ is a nonincreasing function of $h$.

Proof. Monotonicity of $s_{+}$.

1. Let $x\in I$ such that $x\ne b$.

2. Let $h_1,h_2>0$ such that $h_1<h_2$ and $x+h_2\in I$.

3. Consider the three points $x<x+h_1<x+h_2$.

4. Then

   $$\frac{f(x+h_1)-f(x)}{h_1}\le \frac{f(x+h_2)-f(x)}{h_2}.$$

5. Hence $s_{+}(x,h_1)\le s_{+}(x,h_2)$.

6. Hence $s_{+}$ is a nondecreasing function of $h$.

The argument for monotonicity of $s_{-}$ is similar.

Observation 9.6 (One sided derivatives as infimum/supremum)

Due to the monotonicity of $s_{+}$ over $h$, we have

$$f_{+}^{\prime }(x)=\underset{h\downarrow 0}{lim}{s}_{+}(x,h)=\underset{h>0}{inf}{s}_{+}(x,h).$$

Similarly, due to the monotonicity of $s_{+}$ over $h$, we have

$$f_{-}^{\prime }(x)=\underset{h\downarrow 0}{lim}{s}_{-}(x,h)=\underset{h>0}{sup}{s}_{-}(x,h).$$

Theorem 9.200 (Real convex functions and one sided derivatives)

Let $f:\mathbb{R}\to \mathbb{R}$ with $\mathrm{dom}f=I$ be convex. Let $a$ and $b$ be the left and right endpoints of the interval $I$. Then, for every $x\in \mathrm{int}I=(a,b)$, the left hand derivative $f_{-}^{\prime }(x)$ and the right hand derivative $f_{+}^{\prime }(x)$ exist.

If $a\in I$, then the right hand derivative $f_{+}^{\prime }(a)$ exists. If $b\in I$, then the left hand derivative $f_{-}^{\prime }(b)$ exists.

If $a\in I$, we define $f_{-}^{\prime }(a)=-\mathrm{\infty }$. If $b\in I$, we define $f_{+}^{\prime }(b)=\mathrm{\infty }$.

Proof. We are given that $f$ is convex over $(a,b)$.

1. Let $x\in \mathrm{int}I$.

2. Then there exists $r>0$ such that $(x-r,x+r)\subseteq I$.

3. For $h>0$, define

   $$F(h)=\frac{f(x+h)-f(x)}{h}.$$

4. Let $0<h_1<h_2$ such that $h_2<r$.

5. Let $x_1=x$, $x_2=x+h_1$, $x_3=x+h_2$.

6. Since $f$ is convex, hence by Theorem 9.199

   $$\frac{f(x_2)-f(x_1)}{x_2-x_1}\le \frac{f(x_3)-f(x_1)}{x_3-x_1}.$$

7. But that means

$$\frac{f(x+h_1)-f(x)}{h_1}\le \frac{f(x+h_2)-f(x)}{h_2}.$$

1. Thus, whenever $h_1<h_2$ (up to $h_2<r$), $F(h_1)\le F(h_2)$.

2. Thus, $F$ is a nondecreasing (monotone) function of $h$ in some interval $(0,\delta )$ where $\delta <r$.

3. Then, $f_{+}^{\prime }(x)=\underset{h\downarrow 0}{lim}F(h)$ exists.

A similar argument shows that $f_{-}^{\prime }(x)$ also exists. Similar arguments apply for the one sided derivatives at the end points.

9.15.1.3. Continuity

Theorem 9.201 (Convex real function is continuous)

Let $f:\mathbb{R}\to \mathbb{R}$ be a real convex function with $\mathrm{dom}f=I$. Let $a$ and $b$ be the left and right endpoints of the interval $I$. Then,

1. $f$ is continuous at every $x\in (a,b)$.

2. If $a\in I$, then $f$ is continuous from the right at $a$.

3. If $b\in I$, then $f$ is continuous from the left at $b$.

In other words, $f$ is continuous on $I$.

Proof. We proceed as follows.

1. Let $x\in (a,b)$.

2. By Theorem 9.200, the one sided derivatives $f_{+}^{\prime }(x)$ and $f_{-}^{\prime }(x)$ exist.

3. Then, by limit arithmetic

   $$\underset{h\to 0^{-}}{lim}(f(x+h)-f(x))=\left(\underset{h\to 0^{-}}{lim}\frac{f(x+h)-f(x)}{h}\right)\left(\underset{h\to 0^{-}}{lim}h\right)=0.$$

4. Similarly,

   $$\underset{h\downarrow 0}{lim}(f(x+h)-f(x))=\left(\underset{h\downarrow 0}{lim}\frac{f(x+h)-f(x)}{h}\right)\left(\underset{h\downarrow 0}{lim}h\right)=0.$$

5. Thus,

   $$\underset{h\to 0^{-}}{lim}(f(x+h)-f(x))=\underset{h\downarrow 0}{lim}(f(x+h)-f(x))=0.$$

6. Thus, $f$ is continuous at $x$.

7. Since $x$ was arbitrary, hence $f$ is continuous on $(a,b)$.

Now consider the case where $a\in I$.

1. By Theorem 9.200, the one sided derivative $f_{+}^{\prime }(a)$ exists.

2. Then, by limit arithmetic

   $$\underset{h\to 0^{-}}{lim}(f(a+h)-f(a))=\left(\underset{h\to 0^{-}}{lim}\frac{f(a+h)-f(a)}{h}\right)\left(\underset{h\to 0^{-}}{lim}h\right)=0.$$

3. Hence $f$ is continuous from the right at $a$.

A similar argument holds for continuity from the left at $b$.

9.15.1.4. Properties of One Sides Derivatives

Theorem 9.202 (Properties of one-sided derivatives)

Let $f:\mathbb{R}\to \mathbb{R}$ be a real convex function with $\mathrm{dom}f=I$. Let $a$ and $b$ be the left and right endpoints of the interval $I$.

1. We have $f_{-}^{\prime }(x)\le f_{+}^{\prime }(x)$ for every $x\in I$.

2. If $x\in \mathrm{int}I$ then both $f_{-}^{\prime }(x)$ and $f_{+}^{\prime }(x)$ are finite.

3. If $x,z\in I$ and $x<z$, then $f_{+}^{\prime }(x)\le f_{-}^{\prime }(z)$.

4. The functions $f_{-}^{\prime },f_{+}^{\prime }:\mathbb{R}\to \bar{\mathbb{R}}$ are nondecreasing over $I$.

5. The function $f_{+}^{\prime }$ is right-continuous at every interior point of $I$. If $a\in I$ then $f_{+}^{\prime }$ is right-continuous at $a$.

6. The function $f_{-}^{\prime }$ is left-continuous at every interior point of $I$. If $b\in I$ then $f_{-}^{\prime }$ is left-continuous at $b$.

7. The function $f_{+}^{\prime }$ is upper-semicontinuous at every $x\in I$.

8. The function $f_{-}^{\prime }$ is lower-semicontinuous at every $x\in I$.

Proof. (1)

1. If $a\in I$, then by convention $f_{-}^{\prime }(a)=-\mathrm{\infty }$. Hence $f_{-}^{\prime }(a)\le f_{+}^{\prime }(a)$.

2. If $b\in I$, then by convention $f_{+}^{\prime }(b)=\mathrm{\infty }$. Hence $f_{-}^{\prime }(b)\le f_{+}^{\prime }(b)$.

3. Now let $x\in \mathrm{int}I$.

4. Then there is $r>0$ such that $(x-r,x+r)\in I$.

5. Pick any $h>0$ such that $h<r$.

6. Then, using the three points $x-h,x,x+h$, we have

   $$\frac{f(x)-f(x-h)}{h}\le \frac{f(x+h)-f(x)}{h}$$

   due to Theorem 9.199.

7. Taking the limit $h\downarrow 0$, we see that

   $$f_{-}^{\prime }(x)\le f_{+}^{\prime }(x)$$

   holds true for every $x\in \mathrm{int}I$.

(2)

1. Let $x\in \mathrm{int}I$.

2. Let $h>0$ such that $(x-h,x+h)\subseteq I$.

3. Then we have

   $$f_{+}^{\prime }(x)\le \frac{f(x+h)-f(x)}{h}<\mathrm{\infty }.$$

4. Similarly, we have

   $$-\mathrm{\infty }<\frac{f(x)-f(x-h)}{h}\le f_{-}^{\prime }(x).$$

5. By (1), we have

   $$-\mathrm{\infty }<f_{-}^{\prime }(x)\le f_{+}^{\prime }(x)<\mathrm{\infty }.$$

6. Hence both are finite at interior points of $I$.

(3)

1. Let $y=\frac{x+z}{2}$.

2. Due to Theorem 9.199, we have

   $$\frac{f(y)-f(x)}{y-x}\le \frac{f(z)-f(y)}{z-y}.$$

3. We also have

   $$f_{+}^{\prime }(x)\le \frac{f(y)-f(x)}{y-x}\text{ and }\frac{f(z)-f(y)}{z-y}\le f_{-}^{\prime }(z).$$

4. Combining, we get $f_{+}^{\prime }(x)\le f_{-}^{\prime }(z)$.

(4)

1. Let $x,z\in I$ such that $x<z$.

2. From (3), we have $f_{+}^{\prime }(x)\le f_{-}^{\prime }(z)$.

3. From (1), we have $f_{-}^{\prime }(z)\le f_{+}^{\prime }(z)$.

4. Combining, we have $f_{+}^{\prime }(x)\le f_{+}^{\prime }(z)$.

5. Hence $f_{+}^{\prime }$ is nondecreasing.

6. Similarly, $f_{-}^{\prime }(x)\le f_{+}^{\prime }(x)\le f_{-}^{\prime }(z)$.

7. Hence $f_{-}^{\prime }$ is nondecreasing.

(5)

1. Pick any $x\in I$ such that $x\ne b$ (if $b\in I$).

2. Then $x<b$.

3. We can pick $h>0$ and $r>0$ such that $x+h+r<b$.

4. Then $f_{+}^{\prime }(x+h)\le \frac{f(x+h+r)-f(x+h)}{r}$.

5. We established in Theorem 9.201 that $f$ is continuous.

6. Taking the limit $h\downarrow 0$, we obtain

   $$\underset{h\downarrow 0}{lim}{f}_{+}^{\prime }(x+h)\le \frac{f(x+r)-f(x)}{r}.$$

   This is valid since $f$ is continuous.

7. Now taking the limit $r\downarrow 0$ on the R.H.S., we obtain

   $$\underset{h\downarrow 0}{lim}{f}_{+}^{\prime }(x+h)\le f_{+}^{\prime }(x).$$

8. Since $f_{+}^{\prime }$ is nondecreasing by claim (4), hence

   $$f_{+}^{\prime }(x)\le \underset{h\downarrow 0}{lim}{f}_{+}^{\prime }(x+h).$$

9. Together, we must have

   $$f_{+}^{\prime }(x)=\underset{h\downarrow 0}{lim}{f}_{+}^{\prime }(x+h).$$

10. Hence $f_{+}^{\prime }$ is right continuous at $x$.

(6)

1. An argument similar to (5) shows that $f_{-}^{\prime }$ is left continuous at every $x\in I$ except for $x=a$ (if $a\in I$).

(7) Upper semicontinuity of $f_{+}^{\prime }$

1. We need to show that for every $ϵ>0$ there exists $r>0$ such that

   $$f_{+}^{\prime }(y)<f_{+}^{\prime }(x)+ϵ\text{ for every }y\in (x-r,x+r)\cap I.$$

2. Pick some $ϵ>0$.

3. Consider any $x\in \mathrm{int}I$.

4. By (6) $f_{+}^{\prime }$ is right continuous at $x$.

5. Hence there exists $r_1>0$ such that for every $y\in [x,x+r_1)$, we have

   $$|f_{+}^{\prime }(y)-f_{+}^{\prime }(x)|<ϵ.$$

6. By (4), $f_{+}^{\prime }$ is nondecreasing. Hence for every $y\in [x,x+r_1)$

   $$|f_{+}^{\prime }(y)-f_{+}^{\prime }(x)|=f_{+}^{\prime }(y)-f_{+}^{\prime }(x).$$

7. Hence for every $y\in [x,x+r_1)$, we have

   $$f_{+}^{\prime }(y)-f_{+}^{\prime }(x)<ϵ⟺f_{+}^{\prime }(y)<f_{+}^{\prime }(x)+ϵ.$$

8. Now, let $r=min(x-a,r_1)$.

9. By monotonicity of $f_{+}^{\prime }$, for every $y\in (x-r,x)$

   $$f_{+}^{\prime }(y)\le f_{+}^{\prime }(x).$$

10. Hence for every $y\in (x,-r,x)$

    $$f_{+}^{\prime }(y)<f_{+}^{\prime }(x)+ϵ.$$

11. Combining the two, for every $y\in (x-r,x+r)$, we have

    $$f_{+}^{\prime }(y)<f_{+}^{\prime }(x)+ϵ.$$

12. Hence $f_{+}^{\prime }$ is u.s.c. at $x$.

13. Now, if $a\in I$ then let $x=a$.

14. By right continuity of $f_{+}^{\prime }$ at $a$, there exists $r>0$ such that for every $y\in [a,a+r)$, we have

    $$f_{+}^{\prime }(y)<f_{+}^{\prime }(a)+ϵ.$$

15. Also $(a-r,a+r)\cap I=[a,a+r)$.

16. Hence $f_{+}^{\prime }$ is u.s.c. at $a$.

17. If $b\in I$, then by convention $f_{+}^{\prime }(b)=\mathrm{\infty }$.

18. Hence $f_{+}^{\prime }$ is u.s.c. at $b$.

(8) Lower semicontinuity of $f_{-}^{\prime }$

1. The argument is similar to (7).

9.15.2. Directional Derivatives of Proper Functions

Definition 9.70 (Directional derivative)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. The directional derivative at $\mathbf{x}$ in the direction $\mathbf{d}\in \mathbb{V}$ is defined by

$$f^{\prime }(\mathbf{x};\mathbf{d})\triangleq \underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha \mathbf{d})-f(\mathbf{x})}{\alpha }$$

provided the limit exists.

We say that $f$ is directionally differentiable at $\mathbf{x}$ if it is directionally differentiable in every direction at $\mathbf{x}$.

The directional derivative is a scalar quantity ($\in \mathbb{R}$) if it is defined (i.e., the limit exists). When we say that

$$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{t\downarrow 0}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t},$$

we mean that $f$ is defined over a set $\{\mathbf{v}|\mathbf{v}=\mathbf{x}+t\mathbf{d},0<t<t_{max}\}$ and for every $ϵ>0$, there exists $\delta >0$ such that

$$|\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}-f^{\prime }(\mathbf{x};\mathbf{d})|<ϵ\text{ whenever }0<t<\delta .$$

Since $\mathbf{x}\in \mathrm{int}S$, hence there exists $r>0$ such that $B(\mathbf{x},r)\subseteq S$.

With $\mathbf{v}\in B(\mathbf{x},r)$, we need $\Vert t\mathbf{d}\Vert <r$. Thus, a $t_{max}=\frac{r}{\Vert \mathbf{d}\Vert }$ is a suitable range of allowed values for $t$. Accordingly, $0<\delta <t_{max}$ can be chosen.

Remark 9.14 (Directional derivative for zero vector)

If $\mathbf{d}=\mathbf{0}$ then, $f^{\prime }(\mathbf{x};\mathbf{d})=0$.

We can see this from the fact that

$$f^{\prime }(\mathbf{x};\mathbf{0})=\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha \mathbf{0})-f(\mathbf{x})}{\alpha }=0.$$

A useful result is for computing the directional derivative of a function which is the pointwise maximum of a finite number of proper functions.

We recall from Theorem 3.22 that the interior of a finite intersection of sets is the intersection of their interiors. This is useful in identifying the interior of the domain for a pointwise maximum of a finite set of functions.

9.15.3. Differentiability

9.15.3.1. Differentiability of Proper Functions

Definition 9.71 (Differentiability of proper functions)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. $f$ is said to be differentiable at $\mathbf{x}$ if there exists $\mathbf{g}\in {\mathbb{V}}^{\ast }$ such that:

(9.5)$$\underset{\mathbf{h}\to \mathbf{0}}{lim}\frac{f(\mathbf{x}+\mathbf{h})-f(\mathbf{x})-⟨\mathbf{h},\mathbf{g}⟩}{\Vert \mathbf{h}\Vert }=0.$$

The unique vector $\mathbf{g}$ satisfying this condition is called the gradient of $f$ at $\mathbf{x}$ and is denoted by $\mathrm{\nabla }f(\mathbf{x})$.

If $f$ is differentiable at some $\mathbf{x}\in \mathrm{int}S$, then there is a simple formula to connect the gradient and the directional derivatives.

9.15.3.2. Gradient and Directional Derivatives

Theorem 9.203 (Gradient and directional derivatives)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Assume that $f$ is differentiable at $\mathbf{x}$. Then, for any $\mathbf{d}\in \mathbb{V}$,

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.$$

In other words, the directional derivative is the projection of the gradient in the specified direction.

Proof. For $\mathbf{d}=\mathbf{0}$, the equality is obvious. We shall consider the case where $\mathbf{d}\ne \mathbf{0}$.

1. Since $f$ is differentiable at $\mathbf{x}$, hence

$$\underset{\mathbf{h}\to \mathbf{0}}{lim}\frac{f(\mathbf{x}+\mathbf{h})-f(\mathbf{x})-⟨\mathbf{h},\mathrm{\nabla }f(\mathbf{x})⟩}{\Vert \mathbf{h}\Vert }=0.$$

1. In particular, if we take the limit of $\mathbf{h}$ along the direction of $\mathbf{d}$ as $t\mathbf{d}$ where $t>0$ and $t\to 0^{+}$, then

   $$\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})-⟨t\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩}{\Vert t\mathbf{d}\Vert }=0.$$

2. Splitting the terms, we get

   $$\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{\Vert t\mathbf{d}\Vert }-\underset{t\to 0^{+}}{lim}\frac{⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩}{\Vert \mathbf{d}\Vert }=0.$$

3. Multiplying with $\Vert \mathbf{d}\Vert$ and simplifying, we get:

   $$\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}-\underset{t\to 0^{+}}{lim}⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩=0.$$

4. Thus,

   $$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{t\to 0^{+}}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.$$

9.15.3.3. Gradient in ${\mathbb{R}}^n$

Remark 9.15 (Gradient in ${\mathbb{R}}^n$)

It is imperative to compare the definition of gradients in this section with Definition 5.1 (differentiability of functions from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$) and the notion of the gradient as defined in Definition 5.4.

To better develop our understanding of gradients, let us examine the gradient in the Euclidean space ${\mathbb{R}}^n$. The standard basis is given by $\mathcal{B}=\{{\mathbf{e}}_1,\dots ,{\mathbf{e}}_n\}$ which are the coordinate unit vectors. The standard inner product is given by the dot product

$$⟨\mathbf{x},\mathbf{y}⟩={\mathbf{y}}^T\mathbf{x}={\mathbf{x}}^T\mathbf{y}.$$

A vector $\mathbf{x}\in {\mathbb{R}}^n$ is written as

$$\mathbf{x}=\sum _{i=1}^n{x}_i{\mathbf{e}}_i.$$

The individual coordinates are obtained via

$$x_i=⟨{\mathbf{e}}_i,\mathbf{x}⟩=⟨\mathbf{x},{\mathbf{e}}_i⟩={\mathbf{x}}^T{\mathbf{e}}_i\mathrm{\forall }i\in [1,\dots ,n].$$

Let $f:{\mathbb{R}}^n\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper function. Let $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Assume that $f$ is differentiable at $\mathbf{x}$. Let $\mathbf{g}=\mathrm{\nabla }f(\mathbf{x})$. Let

$$\mathbf{g}=\sum _i^n{g}_i{\mathbf{e}}_i.$$

Following the notation in Observation 5.1, the derivative of $f$ at $\mathbf{x}$, denoted by $Df(\mathbf{x})$ is given by

$$\underset{\mathbf{h}\to \mathbf{0}}{lim}\frac{\Vert f(\mathbf{x}+\mathbf{h})-f(\mathbf{x})-Df(\mathbf{x})\mathbf{h}{\Vert }_2}{\Vert \mathbf{h}{\Vert }_2}=0.$$

We don’t have to check for $\mathbf{x}+\mathbf{h}\in \mathrm{dom}f$ as $f$ is a proper function with a value of $\mathrm{\infty }$ at points outside its effective domain.

Compare this with (9.5). For $f:{\mathbb{R}}^n\to \mathbb{R}$, $Df(\mathbf{x})$ is a row vector. If we let $\tilde{\mathbf{g}}=Df(\mathbf{x}{)}^T$, then

$$Df(\mathbf{x})\mathbf{h}={\tilde{\mathbf{g}}}^T\mathbf{h}=⟨\mathbf{h},\tilde{\mathbf{g}}⟩.$$

Then, the definition of $\tilde{\mathbf{g}}$ in the limit above is exactly the same as $\mathbf{g}$ in (9.5). Thus, $\tilde{\mathbf{g}}=\mathbf{g}$. We can see that our definition of gradient coincides with the definition in Definition 5.4 for ${\mathbb{R}}^n$ with the dot product as standard inner product.

Now consider the components of $\mathbf{g}$.

$$g_i=⟨{\mathbf{e}}_i,\mathbf{g}⟩=⟨{\mathbf{e}}_i,\mathrm{\nabla }f(\mathbf{x})⟩.$$

By Theorem 9.203, the directional derivative in the direction ${\mathbf{e}}_i$ is given by

$$f^{\prime }(\mathbf{x};{\mathbf{e}}_i)=⟨{\mathbf{e}}_i,\mathrm{\nabla }f(\mathbf{x})⟩=⟨{\mathbf{e}}_i,\mathbf{g}⟩=g_i.$$

Thus,

$$\frac{\partial f(\mathbf{x})}{\partial x_i}=⟨{\mathbf{e}}_i,\mathrm{\nabla }f(\mathbf{x})⟩.$$

The partial derivatives of $f$ at $\mathbf{x}$ along the standard basis vectors are identical to the directional derivatives of $f$.

$$\begin{array}{r}\mathrm{\nabla }f(\mathbf{x})=\left[\begin{array}{c}\frac{\partial f(\mathbf{x})}{\partial x_1}\\ ⋮\\ \frac{\partial f(\mathbf{x})}{\partial x_n}\end{array}\right]=\left[\begin{array}{c}⟨{\mathbf{e}}_1,\mathrm{\nabla }f(\mathbf{x})⟩\\ ⋮\\ ⟨{\mathbf{e}}_n,\mathrm{\nabla }f(\mathbf{x})⟩\end{array}\right].\end{array}$$

Then, for an arbitrary direction $\mathbf{d}=\sum _{i=1}^n{\mathbf{e}}_i$, the directional derivative becomes

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩=\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}=\sum _{i=1}^n\frac{\partial f(\mathbf{x})}{\partial x_i}{d}_i.$$

Recall from Definition 9.70, that the directional derivative is independent on the choice of the inner product. This is also clear from the expression $\sum _{i=1}^n\frac{\partial f(\mathbf{x})}{\partial x_i}{d}_i$ as the partial derivatives are independent of the choice of the inner product.

However, this means that the gradient itself must depend on the choice of inner product. If $⟨\cdot ,\cdot {⟩}_a$ and $⟨\cdot ,\cdot {⟩}_b$ are two different inner products defined on ${\mathbb{R}}^n$, then the gradients of $f$ at $\mathbf{x}$ w.r.t. the two inner products, denoted by ${\mathrm{\nabla }}_{a}f(\mathbf{x})$ and ${\mathrm{\nabla }}_{b}f(\mathbf{x})$ must satisfy the relationship

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},{\mathrm{\nabla }}_{a}f(\mathbf{x}){⟩}_a=⟨\mathbf{d},{\mathrm{\nabla }}_{b}f(\mathbf{x}){⟩}_b\mathrm{\forall }\mathbf{d}\in \mathbb{V}.$$

In the following, we shall assume that $\mathrm{\nabla }f(\mathbf{x})$ denotes the gradient w.r.t. the dot product.

Consider the inner product given by

$$⟨\mathbf{x},\mathbf{y}{⟩}_H={\mathbf{x}}^T\mathbf{H}\mathbf{y}$$

where $\mathbf{H}\in {\mathbb{R}}^{n\times n}$ is a symmetric positive definite matrix.

Then,

$$\begin{array}{rlr}({\mathrm{\nabla }}_{H}f(\mathbf{x}){)}_i& ={\mathrm{\nabla }}_{H}f(\mathbf{x}{)}^T{\mathbf{e}}_i& \text{coordinate in standard basis}\\ & ={\mathrm{\nabla }}_{H}f(\mathbf{x}{)}^T(\mathbf{H}{\mathbf{H}}^{-1}){\mathbf{e}}_i& \mathbf{H}\text{ is invertible}\\ & ={\mathrm{\nabla }}_{H}f(\mathbf{x}{)}^T\mathbf{H}({\mathbf{H}}^{-1}{\mathbf{e}}_i)& \\ & =⟨{\mathbf{H}}^{-1}{\mathbf{e}}_i,{\mathrm{\nabla }}_{H}f(\mathbf{x}){⟩}_H& \text{by definition of this inner product}\\ & =f^{\prime }(\mathbf{x};{\mathbf{H}}^{-1}{\mathbf{e}}_i)& \text{directional derivative w.r.t. this inner product}\\ & =\mathrm{\nabla }f(\mathbf{x}{)}^T{\mathbf{H}}^{-1}{\mathbf{e}}_i& \text{directional derivative w.r.t. dot product}\\ & =({\mathbf{H}}^{-1}\mathrm{\nabla }f(\mathbf{x}){)}^T{\mathbf{e}}_i& \mathbf{H}\text{ is symmetric}.\end{array}$$

Thus,

$${\mathrm{\nabla }}_{H}f(\mathbf{x})={\mathbf{H}}^{-1}\mathrm{\nabla }f(\mathbf{x}).$$

Thus, the gradient w.r.t. the inner product $⟨\cdot ,\cdot {⟩}_H$ is the scaled version of the standard gradient where the scaling factor is ${\mathbf{H}}^{-1}$.

9.15.3.4. Gradient in ${\mathbb{R}}^{m\times n}$

Remark 9.16 (Gradient in ${\mathbb{R}}^{m\times n}$)

We next look at the vector space of real matrices. The standard basis is a family of unit matrices $\{{\mathbf{E}}_{ij}{\}}_{1\le i\le m,1\le j\le n}$ where ${\mathbf{E}}_{ij}$ has the $(i,j)$-th entry as 1 and other entries as 0.

The standard inner product is given by

$$⟨\mathbf{X},\mathbf{Y}⟩=\mathrm{tr}({\mathbf{Y}}^T\mathbf{X})\mathrm{\forall }\mathbf{X},\mathbf{Y}\in {\mathbb{R}}^{m\times n}.$$

Let $f:{\mathbb{R}}^{m\times n}\to \mathbb{R}$ be a proper function. Let $S=\mathrm{dom}f$. Let $\mathbf{X}\in \mathrm{int}S$. Assume that $f$ is differentiable at $\mathbf{X}$.

The gradient is given by

$$\partial f(\mathbf{X})={\left(\frac{\partial f(\mathbf{X})}{\partial x_{ij}}\right)}_{ij}.$$

The directional derivative for some direction $\mathbf{D}\in {\mathbb{R}}^{m\times n}$ is given by

$$f(\mathbf{X};\mathbf{D})=⟨\mathbf{D},\partial f(\mathbf{X})⟩=\mathrm{tr}(\partial f(\mathbf{X}{)}^T\mathbf{D}).$$

Consider the inner product given by

$$⟨\mathbf{X},\mathbf{Y}{⟩}_H=\mathrm{tr}({\mathbf{X}}^T\mathbf{H}\mathbf{Y})$$

where $\mathbf{H}\in {\mathbb{R}}^{m\times m}$ is a symmetric positive definite matrix.

Then,

$$\begin{array}{rlr}({\mathrm{\nabla }}_{H}f(\mathbf{X}){)}_{ij}& =\mathrm{tr}({\mathrm{\nabla }}_{H}f(\mathbf{X}{)}^T{\mathbf{E}}_{ij})& \text{coordinate in standard basis}\\ & =\mathrm{tr}({\mathrm{\nabla }}_{H}f(\mathbf{X}{)}^T(\mathbf{H}{\mathbf{H}}^{-1}){\mathbf{E}}_{ij})& \mathbf{H}\text{ is invertible}\\ & =\mathrm{tr}({\mathrm{\nabla }}_{H}f(\mathbf{X}{)}^T\mathbf{H}({\mathbf{H}}^{-1}{\mathbf{E}}_{ij}))& \\ & =⟨{\mathbf{H}}^{-1}{\mathbf{E}}_{ij},{\mathrm{\nabla }}_{H}f(\mathbf{X}){⟩}_H& \text{by definition of this inner product}\\ & =f^{\prime }(\mathbf{X};{\mathbf{H}}^{-1}{\mathbf{E}}_{ij})& \text{directional derivative w.r.t. this inner product}\\ & =\mathrm{tr}(\mathrm{\nabla }f(\mathbf{X}{)}^T{\mathbf{H}}^{-1}{\mathbf{E}}_{ij})& \text{directional derivative w.r.t. standard inner product}\\ & =({\mathbf{H}}^{-1}\mathrm{\nabla }f(\mathbf{X}){)}^T{\mathbf{E}}_{ij}& \mathbf{H}\text{ is symmetric}.\end{array}$$

Thus,

$${\mathrm{\nabla }}_{H}f(\mathbf{X})={\mathbf{H}}^{-1}\mathrm{\nabla }f(\mathbf{X}).$$

9.15.4. Proper Convex Functions

9.15.4.1. Existence of Directional Derivatives

An important property of directional derivatives is that if $f$ is a proper convex function then $f$ is directionally differentiable at every $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$.

Theorem 9.204 (Existence of directional derivatives for convex functions.)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Then, for any $\mathbf{d}\in \mathbb{V}$, the directional derivative $f^{\prime }(\mathbf{x};\mathbf{d})$ exists.

Proof. This is a consequence of the directional differentiability of the scalar convex functions.

1. Define the convex function $F:\mathbb{R}\to \mathbb{R}$ as

   $$F(t)=f(\mathbf{x}+t\mathbf{d}).$$

2. Let $I=\mathrm{dom}F$.

3. Then $I$ is an interval of values for which $\mathbf{x}+t\mathbf{y}\in S$.

4. Since $\mathbf{x}\in \mathrm{int}S$, hence $t=0\in \mathrm{int}I$.

5. We now note that

   $$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{t\downarrow 0}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}=\underset{t\downarrow 0}{lim}\frac{F(t)-F(0)}{t}=F_{+}^{\prime }(0).$$

   It is the right hand derivative of $F$ at $t=0$.

6. By Theorem 9.200, $F_{+}^{\prime }(0)$ exists.

7. Hence $f^{\prime }(\mathbf{x};\mathbf{d})$ exists for every $\mathbf{x}\in \mathrm{int}S$ and every $\mathbf{d}\in \mathbb{V}$.

Observation 9.7 (Relation between the directional derivatives in opposite directions)

We can see that

$$f^{\prime }(\mathbf{x};-\mathbf{d})=\underset{t\downarrow 0}{lim}\frac{f(\mathbf{x}-t\mathbf{d})-f(\mathbf{x})}{t}=\underset{t\downarrow 0}{lim}\frac{F(-t)-F(0)}{t}=-\underset{r\uparrow 0}{lim}\frac{F(r)-F(0)}{r}=-F_{-}^{\prime }(0).$$

Hence

$$F_{-}^{\prime }(0)=-f^{\prime }(\mathbf{x};-\mathbf{d}).$$

By Theorem 9.202

$$F_{-}^{\prime }(0)\le F_{+}^{\prime }(0).$$

Hence

$$-f^{\prime }(\mathbf{x};-\mathbf{d})\le f^{\prime }(\mathbf{x};\mathbf{d})\mathrm{\forall }\mathbf{d}\in \mathbb{V}.$$

Observation 9.8 (Directional derivative as infimum)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Then, for any $\mathbf{d}\in \mathbb{V}$,

$$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{t>0}{inf}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}.$$

This follows from the fact that $F(t)=f(\mathbf{x}+t\mathbf{d})$ is convex and due to Observation 9.6,

$$f^{\prime }(\mathbf{x};\mathbf{d})=F_{+}^{\prime }(0)=\underset{t>0}{inf}\frac{F(t)-F(0)}{t}=\underset{t>0}{inf}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}.$$

9.15.4.2. Upper Semicontinuity

The next result generalizes the upper semicontinuity property of the right hand derivatives of real convex functions.

Theorem 9.205

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $\mathrm{dom}f=S$. Assume that $S$ is an open subset of $\mathbb{V}$. Let $\{f_k\}$ be a sequence of proper convex functions $f_k:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ with $\mathrm{dom}{f}_k=S$ with the property that

$$\underset{k\to \mathrm{\infty }}{lim}{f}_k({\mathbf{x}}_k)=f(\mathbf{x})$$

holds true for every $\mathbf{x}\in S$ and every sequence $\{{\mathbf{x}}_k\}$ of $S$ that converges to $\mathbf{x}$. Then for any $\mathbf{x}\in S$ and any direction $\mathbf{d}\in \mathbb{V}$ and any sequences $\{{\mathbf{x}}_k\}$ of $S$ and $\{{\mathbf{d}}_k\}$ of $\mathbb{V}$ converging to $\mathbf{x}$ and $\mathbf{d}$ respectively, we have

$$\underset{k\to \mathrm{\infty }}{lim sup}{f}_k^{\prime }({\mathbf{x}}_k;{\mathbf{d}}_k)\le f^{\prime }(\mathbf{x};\mathbf{d}).$$

Furthermore if $f$ is differentiable over $S$, then $f$ is also continuously differentiable over $S$.

Proof. Limit superior

1. Choose any $ϵ>0$.

2. By definition of the directional derivative, there exists a $t>0$ such that

   $$\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}<f^{\prime }(\mathbf{x};\mathbf{d})+ϵ.$$

3. Due to Observation 9.8, for every $k$ and every $t>0$, we have

   $$f_k^{\prime }({\mathbf{x}}_k;{\mathbf{d}}_k)\le \frac{f_k({\mathbf{x}}_k+t{\mathbf{d}}_k)-f({\mathbf{x}}_k)}{t}.$$

4. Now

   $$\underset{k\to \mathrm{\infty }}{lim}\frac{f_k({\mathbf{x}}_k+t{\mathbf{d}}_k)-f({\mathbf{x}}_k)}{t}=\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}.$$

5. Hence for sufficiently large $k$, we have

   $$f_k^{\prime }({\mathbf{x}}_k;{\mathbf{d}}_k)\le \frac{f_k({\mathbf{x}}_k+t{\mathbf{d}}_k)-f({\mathbf{x}}_k)}{t}<f^{\prime }(\mathbf{x};\mathbf{d})+ϵ.$$

6. By taking the limit superior on the L.H.S. as $k\to \mathrm{\infty }$, we have

   $$\underset{k\to \mathrm{\infty }}{lim sup}{f}_k^{\prime }({\mathbf{x}}_k;{\mathbf{d}}_k)\le f^{\prime }(\mathbf{x};\mathbf{d})+ϵ.$$

7. Since this is valid for every $ϵ>0$, hence we must have

   $$\underset{k\to \mathrm{\infty }}{lim sup}{f}_k^{\prime }({\mathbf{x}}_k;{\mathbf{d}}_k)\le f^{\prime }(\mathbf{x};\mathbf{d})$$

   as desired.

Continuous differentiability

1. We are given that $f$ is differentiable over $S$.

2. Then $f$ is also continuous over $S$.

3. Let $\mathbf{x}\in S$.

4. Let $\{{\mathbf{x}}_k\}$ be a sequence of $S$ converging to $\mathbf{x}$.

5. Let $\mathbf{d}\in \mathbb{V}$ be any nonzero direction.

6. Due to Theorem 9.203, for every $k$,

   $$f^{\prime }({\mathbf{x}}_k;\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩.$$

7. Hence

   $$\begin{array}{rl}\underset{k\to \mathrm{\infty }}{lim sup}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩& =\underset{k\to \mathrm{\infty }}{lim sup}{f}^{\prime }({\mathbf{x}}_k;\mathbf{d})\\ & \le f^{\prime }(\mathbf{x};\mathbf{d})\\ & =⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.\end{array}$$

8. By replacing $\mathbf{d}$ with $-\mathbf{d}$ in the previous argument, we have

   $$\begin{array}{rl}-\underset{k\to \mathrm{\infty }}{lim inf}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩& =\underset{k\to \mathrm{\infty }}{lim sup}⟨-\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩\\ & =\underset{k\to \mathrm{\infty }}{lim sup}{f}^{\prime }({\mathbf{x}}_k;-\mathbf{d})\\ & \le f^{\prime }(\mathbf{x};-\mathbf{d})\\ & =-⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.\end{array}$$

9. Hence

   $$\underset{k\to \mathrm{\infty }}{lim inf}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩\ge ⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.$$

10. Thus we have

    $$\underset{k\to \mathrm{\infty }}{lim sup}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩\le \underset{k\to \mathrm{\infty }}{lim inf}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩.$$

11. But then this must be an equality. Hence

    $$\underset{k\to \mathrm{\infty }}{lim}⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}_k)⟩=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩.$$

12. Since this is valid for every nonzero direction $\mathbf{d}\in \mathbb{V}$, hence we must have

    $$\underset{k\to \mathrm{\infty }}{lim}\mathrm{\nabla }f({\mathbf{x}}_k)=\mathrm{\nabla }f(\mathbf{x}).$$

13. Hence $\mathrm{\nabla }f$ is continuous at every $\mathbf{x}\in S$.

14. Hence $f$ is continuously differentiable at every $\mathbf{x}\in S$.

9.15.4.3. Directional Derivatives Map

The existence of directional derivatives in all directions allows us to consider a mapping from a direction $\mathbf{d}\in \mathbb{V}$ to the directional derivative of $f$ in this direction at $\mathbf{x}$. We can define a directional derivative map parameterized by $\mathbf{x}\in S$ as:

$${\mathbf{g}}_x(\mathbf{d})\triangleq f^{\prime }(\mathbf{x};\mathbf{d})=\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha \mathbf{d})-f(\mathbf{x})}{\alpha }.$$

We shall refer to such maps by $\mathbf{d}\mapsto f^{\prime }(\mathbf{x};\mathbf{d})$.

Theorem 9.206 (Convexity and homogeneity of $\mathbf{d}\mapsto f^{\prime }(\mathbf{x};\mathbf{d})$)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Then, the function $\mathbf{d}\mapsto f^{\prime }(\mathbf{x};\mathbf{d})$ is convex and nonnegative homogeneous.

Nonnegative homogeneity: For any $t\ge 0$ and $\mathbf{d}\in \mathbb{V}$,

$$f^{\prime }(\mathbf{x};t\mathbf{d})=t{f}^{\prime }(\mathbf{x};\mathbf{d}).$$

Proof. Convexity

1. Let ${\mathbf{d}}_1,{\mathbf{d}}_2\in \mathbb{V}$ and $t\in (0,1)$.

2. Let $\mathbf{d}=t{\mathbf{d}}_1+(1-t){\mathbf{d}}_2$.

3. Then,

   $$\begin{array}{rl}{f}^{\prime }(\mathbf{x};\mathbf{d})& =f^{\prime }(\mathbf{x};t{\mathbf{d}}_1+(1-t){\mathbf{d}}_2)\\ & =\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha [t{\mathbf{d}}_1+(1-t){\mathbf{d}}_2])-f(\mathbf{x})}{\alpha }\\ & =\underset{\alpha \downarrow 0}{lim}\frac{f(t\mathbf{x}+\alpha t{\mathbf{d}}_1+(1-t)\mathbf{x}+\alpha (1-t){\mathbf{d}}_2)-f(\mathbf{x})}{\alpha }\\ & =\underset{\alpha \downarrow 0}{lim}\frac{f(t(\mathbf{x}+\alpha {\mathbf{d}}_1)+(1-t)(\mathbf{x}+\alpha {\mathbf{d}}_2))-f(\mathbf{x})}{\alpha }\\ & \le \underset{\alpha \downarrow 0}{lim}\frac{tf(\mathbf{x}+\alpha {\mathbf{d}}_1)+(1-t)f(\mathbf{x}+\alpha {\mathbf{d}}_2)-tf(\mathbf{x})-(1-t)f(\mathbf{x})}{\alpha }\\ & =t\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha {\mathbf{d}}_1)-f(\mathbf{x})}{\alpha }+(1-t)\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha {\mathbf{d}}_2)-f(\mathbf{x})}{\alpha }\\ & =t{f}^{\prime }(\mathbf{x};{\mathbf{d}}_1)+(1-t)f^{\prime }(\mathbf{x};{\mathbf{d}}_2).\end{array}$$

   We used the convexity property of $f$ in this derivation.

4. Thus, $f^{\prime }(\mathbf{x};\mathbf{d})$ is convex.

Nonnegative homogeneity

1. For $t=0$,

   $$f^{\prime }(\mathbf{x},0\mathbf{d})=f^{\prime }(\mathbf{x},\mathbf{0})=0=0f^{\prime }(\mathbf{x};\mathbf{d}).$$

   Thus, the homogeneity property is trivial for $t=0$.

2. Now consider $t>0$.

3. Then,

   $$\begin{array}{rl}{f}^{\prime }(\mathbf{x};t\mathbf{d})& =\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha t\mathbf{d})-f(\mathbf{x})}{\alpha }\\ & =t\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha t\mathbf{d})-f(\mathbf{x})}{\alpha t}\\ & =t{f}^{\prime }(\mathbf{x};\mathbf{d}).\end{array}$$

4. Thus, $f^{\prime }(\mathbf{x};\mathbf{d})$ is nonnegative homogeneous.

9.15.4.4. As Linear Underestimator

Directional derivatives are a linear underestimator for convex functions.

Theorem 9.207 (Directional derivative as linear underestimator)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $S=\mathrm{dom}f$. Let $\mathbf{x}\in \mathrm{int}S$. Then, for every $\mathbf{y}\in S$

$$f(\mathbf{y})\ge f(\mathbf{x})+f^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x}).$$

Proof. Note that

$$\begin{array}{rl}{f}^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x})& =\underset{\alpha \downarrow 0}{lim}\frac{f(\mathbf{x}+\alpha (\mathbf{y}-\mathbf{x}))-f(\mathbf{x})}{\alpha }\\ & =\underset{\alpha \downarrow 0}{lim}\frac{f((1-\alpha )\mathbf{x}+\alpha \mathbf{y})-f(\mathbf{x})}{\alpha }\\ & \le \underset{\alpha \downarrow 0}{lim}\frac{(1-\alpha )f(\mathbf{x})+\alpha f(\mathbf{y})-f(\mathbf{x})}{\alpha }\\ & =\underset{\alpha \downarrow 0}{lim}\frac{\alpha (f(\mathbf{y})-f(\mathbf{x}))}{\alpha }\\ & =\underset{\alpha \downarrow 0}{lim}(f(\mathbf{y})-f(\mathbf{x}))=f(\mathbf{y})-f(\mathbf{x}).\end{array}$$

Thus,

$$f(\mathbf{y})\ge f(\mathbf{x})+f^{\prime }(\mathbf{x};\mathbf{y}-\mathbf{x}).$$

9.15.5. Pointwise Maximum of Finite Set of Functions

9.15.5.1. Directional Derivative

Theorem 9.208 (Directional derivative of a maximum of functions)

Let $f_1,f_2,\dots ,f_m:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be proper functions. Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be defined as

$$f(\mathbf{x})=max\{f_1(\mathbf{x}),\dots ,f_m(\mathbf{x})\}$$

with $\mathrm{dom}f=\bigcap _{i=1}^m\mathrm{dom}{f}_i$.

Let $\mathbf{x}\in \mathrm{int}\mathrm{dom}f=\bigcap _{i=1}^m\mathrm{int}\mathrm{dom}{f}_i$ and $\mathbf{d}\in \mathbb{V}$. Assume that $f^{\prime }(\mathbf{x};\mathbf{d})$ exists for every $i\in 1,\dots ,m$.

Let $I(\mathbf{x})=\{i\in 1,\dots ,m|f_i(\mathbf{x})=f(\mathbf{x})\}$ be the set of indices of functions whose value at $\mathbf{x}$ equals $f(\mathbf{x})$. Then,

$$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{i\in I(\mathbf{x})}{max}{f}^{\prime }(\mathbf{x};\mathbf{d}).$$

In other words, the directional derivative of a pointwise maximum of functions equals the maximum of directional directives of functions which attain the pointwise maximum at a specific point.

Proof. The key idea here is that for computing the directional derivative $f^{\prime }(\mathbf{x};\mathbf{d})$, only those functions are relevant for which $f_i(\mathbf{x})=f(\mathbf{x})$. We need to show this first.

1. Since $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$, there exists $B(\mathbf{x},r)$ such that $f$ and $f_i$ are all defined over this open ball.

2. Let $s=\frac{r}{\Vert \mathbf{d}\Vert }$.

3. For every $i\in 1,\dots ,m$, let $g_i:\mathbb{R}\to \mathbb{R}$ be defined as

   $$g_i(t)=f_i(\mathbf{x}+t\mathbf{d})$$

   with $\mathrm{dom}{g}_i=[0,s)$. $\Vert s\mathbf{d}\Vert =r$. Thus, $\mathbf{x}+t\mathbf{d}\in B(\mathbf{x},r)$. Hence, $g_i$ are well defined.

4. Then,

   $$\begin{array}{rl}\underset{t\to 0+}{lim}{g}_i(t)& =\underset{t\to 0+}{lim}{f}_i(\mathbf{x}+t\mathbf{d})\\ & =\underset{t\to 0+}{lim}[(f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x}))+f_i(\mathbf{x})]\\ & =\underset{t\to 0+}{lim}[t\frac{f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x})}{t}+f_i(\mathbf{x})]\\ & =0\cdot f_i^{\prime }(\mathbf{x};\mathbf{d})+f_i(\mathbf{x})\\ & =f_i(\mathbf{x})=g_i(0).\end{array}$$

   We used the fact that $f_i^{\prime }(\mathbf{x};\mathbf{d})$ exists for every $f_i$.

5. Thus, $g_i$ is continuous from the right at $t=0$ for every $i\in 1,\dots ,m$.

6. Let $i\in I(\mathbf{x})$ and $j\notin I(\mathbf{x})$.

7. Then, $f_i(\mathbf{x})>f_j(\mathbf{x})$. Alternatively $g_i(0)>g_j(0)$.

8. Since $g_i,g_j$ are continuous from the right, hence there exists ${ϵ}_{ij}>0$ such that $g_i(t)>g_j(t)$ for every $t\in [0,{ϵ}_{ij}]$.

9. Minimizing ${ϵ}_{ij}$ over all pairs of $i\in I(\mathbf{x})$ and $j\notin I(\mathbf{x})$, there exists $ϵ>0$ such that for any $i\in I(\mathbf{x})$ and $j\notin I(\mathbf{x})$,

   $$f_i(\mathbf{x}+t\mathbf{d})=g_i(t)>g_j(t)=f_j(\mathbf{x}+t\mathbf{d})\mathrm{\forall }t\in [0,ϵ].$$

We can now compute the directional derivative.

1. For every $t\in [0,ϵ]$,

   $$f(\mathbf{x}+t\mathbf{d})=\underset{i=1,\dots ,m}{max}{f}_i(\mathbf{x}+t\mathbf{d})=\underset{i\in I(\mathbf{x})}{max}{f}_i(\mathbf{x}+t\mathbf{d}).$$

2. Consequently, for any $t\in (0,ϵ]$

   $$\begin{array}{rl}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}& =\frac{\underset{i\in I(\mathbf{x})}{max}{f}_i(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}\\ & =\frac{\underset{i\in I(\mathbf{x})}{max}(f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x}))}{t}\\ & =\underset{i\in I(\mathbf{x})}{max}\frac{f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x})}{t}.\end{array}$$

   We used the fact that $f_i(\mathbf{x})=f(\mathbf{x})$ for every $i\in I(\mathbf{x})$.

3. Taking the limit $t\downarrow 0$,

   $$\begin{array}{rl}{f}^{\prime }(\mathbf{x};\mathbf{d})& =\underset{t\downarrow 0}{lim}\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}\\ & =\underset{t\downarrow 0}{lim}\underset{i\in I(\mathbf{x})}{max}\frac{f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x})}{t}\\ & =\underset{i\in I(\mathbf{x})}{max}\underset{t\downarrow 0}{lim}\frac{f_i(\mathbf{x}+t\mathbf{d})-f_i(\mathbf{x})}{t}\\ & =\underset{i\in I(\mathbf{x})}{max}{f}_i^{\prime }(\mathbf{x};\mathbf{d}).\end{array}$$

9.15.5.2. Finite Set of Convex Functions Case

Theorem 9.209 (Directional derivative of pointwise maximum of convex functions)

Let $f_1,f_2,\dots ,f_m:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be proper convex functions. Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be defined as

$$f(\mathbf{x})=max\{f_1(\mathbf{x}),\dots ,f_m(\mathbf{x})\}$$

with $\mathrm{dom}f=\bigcap _{i=1}^m\mathrm{dom}{f}_i$.

Let $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$ and $\mathbf{d}\in \mathbb{V}$. Then,

$$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{i\in I(\mathbf{x})}{max}{f}^{\prime }(\mathbf{x};\mathbf{d}).$$

where $I(\mathbf{x})=\{i\in 1,\dots ,m|f_i(\mathbf{x})=f(\mathbf{x})\}$.

Proof. Since $f_i$ are proper convex, hence their pointwise maximum $f$ is proper convex.

By Theorem 9.204, the directional derivatives $f^{\prime }(\mathbf{x};\mathbf{d})$ and $f_i^{\prime }(\mathbf{x};\mathbf{d})$ for $i=1,\dots ,m$ exist.

By Theorem 9.208,

$$f^{\prime }(\mathbf{x};\mathbf{d})=\underset{i\in I(\mathbf{x})}{max}{f}^{\prime }(\mathbf{x};\mathbf{d}).$$

where $I(\mathbf{x})=\{i\in 1,\dots ,m|f_i(\mathbf{x})=f(\mathbf{x})\}$.