5.3.1 One-sided differentials

Let $v:\mathbb{R}^n\to \mathbb{R}$ be a continuous function (nothing beyond continuity is required from $v$ ). A vector $\xi\in\mathbb{R}^n$ is called a super-differential of $v$ at a given point $x$ if for all $y$ near $x$ we have the relation

$$v(y)\le v(x)+\langle \xi,y-x\rangle +o(\vert y-x\vert).$$ (5.27)

Geometrically, $\xi$ is a super-differential if the graph of the linear function $y\mapsto v(x)+\langle \xi,y-x\rangle$ , which has $\xi$ as its gradient and takes the value $v(x)$ at $y=x$ , lies above the graph of $v$ at least locally near $x$ (or is tangent to the graph of $v$ at $x$ ). Figure 5.5(a) illustrates this situation for the scalar case ($n=1$ ), in which $\xi$ is the slope of the line. A super-differential $\xi$ is in general not unique; we thus have a set of super-differentials of $v$ at $x$ , which is denoted by $D^+v(x)$ .

Figure: (a) super-differential, (b) sub-differential

                

Similarly, we say that $\xi\in\mathbb{R}^n$ is a sub-differential of $v$ at $x$ if

$$v(y)\ge v(x)+\langle \xi,y-x\rangle -o(\vert y-x\vert).$$ (5.28)

The graph of the linear function with gradient $\xi$ touching the graph of $v$ at $x$ must now lie below the graph of $v$ in a vicinity of $x$ (or be tangent to it at $x$ ); see Figure 5.5(b). The set of sub-differentials of $v$ at $x$ is denoted by $D^-v(x)$ .

Figure: The function in Example 5.3

We now establish some useful properties of super- and sub-differentials.

TEST FUNCTIONS. $\xi\in D^+ v(x)$ if and only if there exists a $\mathcal C^1$ function $\varphi:\mathbb{R}^n\to\mathbb{R}$ such that $\nabla \varphi(x)=\xi$ , $\varphi(x)=v(x)$ , and $\varphi(y)\ge v(y)$ for all $y$ near $x$ , i.e., $\varphi-v$ has a local minimum at $x$ . Similarly, $\xi\in D^- v(x)$ if and only if there exists a $\mathcal C^1$ function $\varphi$ such that $\nabla \varphi(x)=\xi$ and $\varphi-v$ has a local maximum at $x$ . (Note that we can always arrange to have $\varphi(x)=v(x)$ by adding a constant to $\varphi$ , which does not affect the other conditions.)

Figure: Characterization of a super-differential via a test function

The function $\varphi$ is sometimes called a test function. For the case of $D^+v(x)$ , an example of such a function is shown in Figure 5.7. The above result, whose proof we will not give, will be used for proving the other facts that follow.

RELATION WITH CLASSICAL DIFFERENTIALS. If $v$ is differentiable at $x$ , then

$$D^+v(x)=D^-v(x)=\{\nabla v(x)\}.$$ (5.29)

If $D^+v(x)$ and $D^-v(x)$ are both nonempty, then $v$ is differentiable at $x$ and the relation (5.33) holds.

We prove both claims with the help of test functions. First, suppose that $v$ is differentiable at $x$ . It is clear that the gradient $\nabla v(x)$ is both a super-differential and a sub-differential of $v$ at $x$ (indeed, with $\xi=\nabla v(x)$ both (5.31) and (5.32) become equalities). If $\varphi-v$ has a local minimum or maximum at $x$ for some $\varphi\in\mathcal C^1$ , then $\nabla(\varphi-v)(x)=0$ hence $\nabla \varphi(x)=\nabla v(x)$ . This shows that $\xi=\nabla v(x)$ is the only element in $D^+v(x)$ and $D^-v(x)$ .

To prove the second claim, let $\varphi_1,\varphi_2\in\mathcal C^1$ be such that $\varphi_1(x)=v(x)=\varphi_2(x)$ and $\varphi_1(y)\le v(y)\le\varphi_2(y)$ for $y$ near $x$ . Then $\varphi_1-\varphi_2$ has a local maximum at $x$ , implying that $\nabla(\varphi_1-\varphi_2)(x)=0$ hence $\nabla\varphi_1(x)=\nabla\varphi_2(x)$ . For $y>x$ (the case $y<x$ is completely analogous) we can write

$$\frac{\varphi_1(y)-\varphi_1(x)}{y-x}\le \frac{v(y)-v(x)}{y-x}\le \frac{\varphi_2(y)-\varphi_2(x)}{y-x}.$$

As $y\to x$ , the first fraction approaches $\nabla\varphi_1(x)$ , the last one approaches $\nabla\varphi_2(x)$ , and we know that the two gradients are equal. Therefore, by the ``Sandwich Theorem" the limit of the middle fraction exists and equals the other two. This limit must be $\nabla v(x)$ , and everything is proved.

NON-EMPTINESS AND DENSENESS. The sets $\{x: D^+v(x)\ne\emptyset\}$ and $\{x: D^-v(x)\ne\emptyset\}$ are both nonempty, and actually dense in the domain of $v$ .

The idea of the proof is sketched in Figure 5.8. The highly irregular graph in the figure is that of $v$ . Take an arbitrary point $x_0$ . Choosing a $\mathcal C^1$ function $\varphi$ steep enough (see the solid curve in the figure), we can force $\varphi-v$ to have a local maximum at a nearby point $x$ , as close to $x_0$ as we want. (For clarity, we also shift the graph of $\varphi$ vertically to produce the dotted curve in the figure which touches the graph of $v$ at $x$ .) We then have $\nabla\varphi(x)\in D^-v(x)$ . A similar argument works for $D^+$ .

Figure: Proving denseness