# Subdifferentials of convex functions

## 1 Introduction

Whenever we speak about a vector space in this note we mean a vector space over $\mathbb{R}$. If $X$ is a topological vector space then
we denote by ${X}^{*}$ the set of all continuous linear maps $X\to \mathbb{R}$. ${X}^{*}$ is called the dual space of $X$, and is itself a vector space.^{1}^{1}
1
In this note,
we are
following the presentation of some results in Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., chapter 7. Three other sources
for material on subdifferentials are: Jean-Paul Penot, Calulus Without Derivatives, chapter 3; Viorel Barbu and Teodor Precupanu, Convexity and Optimization in Banach Spaces, fourth ed., §2.2, pp. 82–125;
and Jean-Pierre Aubin, Optima and Equilibria: An Introduction to Nonlinear Analysis, second ed., chapter 4, pp. 57–73.

## 2 Definition of subdifferential

If $X$ is a topological vector space, $f:X\to [-\mathrm{\infty},\mathrm{\infty}]$ is a function, $x\in X$, and $\lambda \in {X}^{*}$, then we say that $\lambda $ is a
subgradient of $f$ at $x$ if^{2}^{2}
2
$\mathrm{\infty}+\mathrm{\infty}=\mathrm{\infty}$, $-\mathrm{\infty}-\mathrm{\infty}=-\mathrm{\infty}$, and $\mathrm{\infty}-\mathrm{\infty}$ is nonsense; if $a\in \mathbb{R}$, then $a-\mathrm{\infty}=-\mathrm{\infty}$ and $a+\mathrm{\infty}=\mathrm{\infty}$.

$$f(y)\ge f(x)+\lambda (y-x),y\in X.$$ |

The subdifferential of $f$ at $x$ is the set of all subgradients of $f$ at $x$ and is denoted by $\partial f(x)$. Thus $\partial f$ is a function from $X$ to the power set of ${X}^{*}$, i.e. $\partial f:X\to {2}^{{X}^{*}}$. If $\partial f(x)\ne \mathrm{\varnothing}$, we say that $f$ is subdifferentiable at $x$.

It is immediate that if there is some $y$ such that $f(y)=-\mathrm{\infty}$, then

$$\partial f(x)=\{\begin{array}{cc}{X}^{*}\hfill & f(x)=-\mathrm{\infty}\hfill \\ \mathrm{\varnothing}\hfill & f(x)>-\mathrm{\infty}\hfill \end{array},x\in X.$$ |

Thus, little is lost if we prove statements about subdifferentials of functions that do not take the value $-\mathrm{\infty}$.

###### Theorem 1.

If $X$ is a topological vector space, $f\mathrm{:}X\mathrm{\to}\mathrm{[}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a function and $x\mathrm{\in}X$, then $\mathrm{\partial}\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}$ is a convex subset of ${X}^{\mathrm{*}}$.

###### Proof.

If ${\lambda}_{1},{\lambda}_{2}\in \partial f(x)$ and $0\le t\le 1$, then of course $(1-t){\lambda}_{1}+t{\lambda}_{2}\in {X}^{*}$. For any $y\in X$ we have

$f(y)$ | $=(1-t)f(y)+tf(y)$ | ||

$\ge (1-t)f(x)+(1-t){\lambda}_{1}(y-x)+tf(x)+t{\lambda}_{2}(y-x)$ | |||

$=f(x)+\left((1-t){\lambda}_{1}+t{\lambda}_{2}\right)(y-x),$ |

showing that $(1-t){\lambda}_{1}+t{\lambda}_{2}\in \partial f(x)$ and thus that $\partial f(x)$ is convex. ∎

To say that $0\in \partial f(x)$ is equivalent to saying that $f(y)\ge f(x)$ for all $y\in X$ and so $f(x)={inf}_{y\in X}f(y)$. This can be said in the following way.

###### Lemma 2.

If $X$ is a topological vector space and $f\mathrm{:}X\mathrm{\to}\mathrm{[}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a function, then $x$ is a minimizer of $f$ if and only if $\mathrm{0}\mathrm{\in}\mathrm{\partial}\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}$.

## 3 Convex functions

If $X$ is a set and $f:X\to [-\mathrm{\infty},\mathrm{\infty}]$ is a function, then the epigraph of $f$ is the set

$$\mathrm{epi}f=\{(x,\alpha )\in X\times \mathbb{R}:\alpha \ge f(x)\},$$ |

and the effective domain of $f$ is the set

$$ |

To say that $x\in \mathrm{dom}f$ is equivalent to saying that there is some $\alpha \in \mathbb{R}$ such that $(x,\alpha )\in \mathrm{epi}f$. We say that $f$ is finite if $$ for all $x\in X$.

If $X$ is a vector space and $f:X\to [-\mathrm{\infty},\mathrm{\infty}]$ is a function, then we say that $f$ is convex if $\mathrm{epi}f$ is a convex subset of the vector space $X\times \mathbb{R}$.

If $X$ is a set and $f:X\to [-\mathrm{\infty},\mathrm{\infty}]$ is a function, we say that $f$ is proper if it does not take only the value $\mathrm{\infty}$ and never takes the value $-\mathrm{\infty}$. It is unusual to talk merely about proper functions rather than proper convex functions; we do so to make clear how convexity is used in the results we prove.

## 4 Weak-* topology

Let $X$ be a topological vector space and for $x\in X$ define ${e}_{x}:{X}^{*}\to \mathbb{R}$ by ${e}_{x}\lambda =\lambda x$. The weak-* topology on ${X}^{*}$ is the initial topology for the set of functions $\{{e}_{x}:x\in X\}$, that is, the coarsest topology on ${X}^{*}$ such that for each $x\in X$, the function ${e}_{x}:{X}^{*}\to \mathbb{R}$ is continuous.

###### Lemma 3.

If $X$ is a topological vector space, ${\tau}_{\mathrm{1}}$ is the weak-* topology on ${X}^{\mathrm{*}}$, and ${\tau}_{\mathrm{2}}$ is the subspace topology on ${X}^{\mathrm{*}}$ inherited from ${\mathrm{R}}^{X}$ with the product topology, then ${\tau}_{\mathrm{1}}\mathrm{=}{\tau}_{\mathrm{2}}$.

###### Proof.

Let ${\lambda}_{i}\in {X}^{*}$ converge in ${\tau}_{1}$ to $\lambda \in {X}^{*}$. For each $x\in X$, the function ${e}_{x}:{X}^{*}\to \mathbb{R}$ is ${\tau}_{1}$ continuous, so ${e}_{x}{\lambda}_{i}\to {e}_{x}\lambda $, i.e. ${\lambda}_{i}x\to \lambda x$. But for ${f}_{i}\in {\mathbb{R}}^{X}$ to converge to $f\in {\mathbb{R}}^{X}$ means that for each $x$, we have ${f}_{i}(x)\to f(x)$. Thus ${\lambda}_{i}$ converges to $\lambda $ in ${\tau}_{2}$. This shows that ${\tau}_{2}\subseteq {\tau}_{1}$.

Let $x\in X$, and let ${\lambda}_{i}\in {X}^{*}$ converge in ${\tau}_{2}$ to $\lambda \in {X}^{*}$. We then have ${e}_{x}{\lambda}_{i}={\lambda}_{i}x\to \lambda x={e}_{x}\lambda $; since ${\lambda}_{i}$ was an arbitrary net that converges in ${\tau}_{2}$, this shows that ${e}_{x}$ is ${\tau}_{2}$ continuous. Thus, we have shown that for each $x\in X$, the function ${e}_{x}$ is ${\tau}_{2}$ continuous. But ${\tau}_{1}$ is the coarsest topology for which ${e}_{x}$ is continuous for all $x\in X$, so we obtain ${\tau}_{1}\subseteq {\tau}_{2}$. ∎

In other words, the weak-* topology on ${X}^{*}$ is the topology of pointwise convergence.
We now prove that
at each point in the effective domain of a proper function on a topological vector space,
the subdifferential is a weak-* closed subset of the dual space.^{3}^{3}
3
cf. Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., p. 265, Theorem 7.13.

###### Theorem 4.

If $X$ is a topological vector space, $f\mathrm{:}X\mathrm{\to}\mathrm{(}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a proper function, and $x\mathrm{\in}\mathrm{dom}\mathit{}f$, then $\mathrm{\partial}\mathit{}f\mathit{}\mathrm{(}x\mathrm{)}$ is a weak-* closed subset of ${X}^{\mathrm{*}}$.

###### Proof.

If $\lambda \in \partial f(x)$, then for all $y\in X$ we have

$$f(y)\ge f(x)+\lambda (y-x),$$ |

so, for any $v\in X$, using $y=v+x$,

$$f(v+x)\ge f(x)+\lambda v,$$ |

or,

$$\lambda v\le f(x+v)-f(x);$$ |

this makes sense because $f(x)$ is finite. On the other hand, let $\lambda \in {X}^{*}$. If $\lambda v\le f(x+v)-f(x)$ for all $v\in X$, then $\lambda (v-x)\le f(v)-f(x)$, i.e. $f(v)\ge f(x)+\lambda (v-x)$, and so $\lambda \in \partial f(x)$. Therefore

$$\partial f(x)=\bigcap _{v\in X}\{\lambda \in {X}^{*}:\lambda v\le f(x+v)-f(x)\}.$$ | (1) |

Defining ${e}_{v}:{X}^{*}\to \mathbb{R}$ for $v\in X$ by ${e}_{v}\lambda =\lambda v$, for each $v\in X$ we have

$${e}_{v}^{-1}(-\mathrm{\infty},f(x+v)-f(x)]=\{\lambda \in {X}^{*}:\lambda v\le f(x+v)-f(x)\}.$$ |

Because ${e}_{v}$ is continuous, this inverse image is a closed subset of ${X}^{*}$. Therefore, each of the sets in the intersection (1) is a closed subset of ${X}^{*}$, and so $\partial f(x)$ is a closed subset of ${X}^{*}$. ∎

## 5 Support points

If $X$ is set, $A$ is a subset of $X$, and $f:X\to [-\mathrm{\infty},\mathrm{\infty}]$ is a function, we say that $x\in X$ is a minimizer of $f$ over $A$ if

$$f(x)=\underset{y\in A}{inf}f(y),$$ |

and that $x$ is a maximizer of $f$ over $A$ if

$$f(x)=\underset{y\in A}{sup}f(y).$$ |

If $A$ is a nonempty subset of a topological vector space $X$ and $x\in A$, we say that $x$ is a support point of $A$ if there is some nonzero $\lambda \in {X}^{*}$ for which $x$ is a minimizer or a maximizer of $\lambda $ over $A$. Moreover, $x$ is a minimizer of $\lambda $ over $A$ if and only if $x$ is a maximizer of $-\lambda $ over $A$. Thus, if we know that $x$ is a support point of a set $A$, then we have at our disposal both that $x$ is a minimizer of some nonzero element of ${X}^{*}$ over $A$ and that $x$ is a maximizer of some nonzero element of ${X}^{*}$ over $A$.

If $x$ is a support point of $A$ and $A$ is not contained in the hyperplane $\{y\in X:\lambda y=\lambda x\}$, we say that $A$ is properly supported at $x$. To say that $A$ is not contained in the set $\{y\in X:\lambda y=\lambda x\}$ is equivalent to saying that there is some $y\in A$ such that $\lambda y\ne \lambda x$.

In the following lemma, we show that the support points of a set $A$ are contained in the boundary $\partial A$ of the set.

###### Lemma 5.

If $X$ is a topological vector space, $A$ is a subset of $X$, and $x$ is a support point of $A$, then $x\mathrm{\in}\mathrm{\partial}\mathit{}A$.

###### Proof.

Because $x$ is a support point of $A$ there is some nonzero $\lambda \in {X}^{*}$ for which $x$ is a maximizer of $\lambda $ over $A$:

$$\lambda x=\underset{y\in A}{sup}\lambda y.$$ |

As $\lambda $ is nonzero there is some $y\in X$ with $\lambda y>\lambda x$. For any $t>0$,

$$(1-t)\lambda x+t\lambda y=\lambda ((1-t)x+ty)=(1-t)\lambda x+t\lambda y>(1-t)\lambda x+t\lambda x=\lambda x,$$ |

hence if $t>0$ then $(1-t)\lambda x+ty\notin A$. But $(1-t)x+ty\to x$ as $t\to 0$ and $x\in A$, showing that $x\in \partial A$. ∎

The following lemma gives conditions under which a boundary point of a set is a proper support point of the set.^{4}^{4}
4
Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., p. 259, Lemma 7.7.

###### Lemma 6.

If $X$ is a topological vector space, $C$ is a convex subset of $X$ that has nonempty interior, and $x\mathrm{\in}C\mathrm{\cap}\mathrm{\partial}\mathit{}C$, then $C$ is properly supported at $x$.

###### Proof.

The Hahn-Banach separation theorem^{5}^{5}
5
Gert K. Pedersen, Analysis Now, revised printing, p. 65, Theorem 2.4.7. tells us that if
$A$ and $B$ are disjoint nonempty convex subsets of $X$ and $A$ is open then there is some $\lambda \in {X}^{*}$ and some $t\in \mathbb{R}$ such that

$$ |

Check that the interior of a convex set in a topological vector space is convex, and hence that we can apply the Hahn-Banach separation theorem to $\{x\}$ and ${C}^{\circ}$: as $x$ belongs to the boundary of $C$ it does not belong to the interior of $C$, so $\{x\}$ and ${C}^{\circ}$ are disjoint nonempty convex sets. Thus, there is some $\lambda \in {X}^{*}$ and some $t\in \mathbb{R}$ such that $$ for all $y\in {C}^{\circ}$, from which it follows that $\lambda x\le \lambda y$ for all $y\in C$, and $\lambda \ne 0$ because of the strict inequality for the interior. As $x\in C$, this means that $x$ is a maximizer of $\lambda $ over $C$, and as $\lambda \ne 0$ this means that $x$ is a support point of $C$. But ${C}^{\circ}$ is nonempty and if $y\in {C}^{\circ}$ then $$, hence $x$ is a proper support point of $C$. ∎

## 6 Subdifferentials of convex functions

If $f:X\to (-\mathrm{\infty},\mathrm{\infty}]$ is a proper function then there is some $y\in X$ for which $$, and for $f$ to have a subgradient $\lambda $ at $x$ demands that $f(y)\ge f(x)+\lambda (y-x)$, and hence that $$. Therefore, if $f$ is a proper function then the set of $x$ at which $f$ is subdifferentiable is a subset of $\mathrm{dom}f$.

We now prove conditions under which a function is subdifferentiable at a point, i.e., under which the subdifferential at that point is nonempty.^{6}^{6}
6
Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., p. 265, Theorem 7.12.

###### Theorem 7.

If $X$ is a topological vector space, $f\mathrm{:}X\mathrm{\to}\mathrm{(}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a proper convex function, $x$ is an interior point of $\mathrm{dom}\mathit{}f$, and $f$ is continuous at $x$, then $f$ has a subgradient at $x$.

###### Proof.

Because $f$ is convex, the set $\mathrm{dom}f$ is convex, and the interior of a convex set in a topological vector space is convex so ${(\mathrm{dom}f)}^{\circ}$ is convex.
$f$ is proper so it does not take the value $-\mathrm{\infty}$, and on $\mathrm{dom}f$ it does not take the value $\mathrm{\infty}$, hence $f$ is finite on $\mathrm{dom}f$.
But for a finite convex function on an open convex set in a topological vector space, being continuous at a point
is equivalent to being continuous on the set, and is also equivalent to being bounded above on an open neighborhood of the point.^{7}^{7}
7
Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., p. 188, Theorem 5.43.
Therefore, $f$ is continuous on ${(\mathrm{dom}f)}^{\circ}$ and is bounded above on some open neighborhood $V$ of $x$ contained in ${(\mathrm{dom}f)}^{\circ}$, say $f(y)\le M$ for all $y\in V$.
$V\times (M,\mathrm{\infty})$ is an open subset of $X\times \mathbb{R}$, and is contained in $\mathrm{epi}f$. This shows that $\mathrm{epi}f$ has nonempty interior.
Since $$, if $\u03f5>0$ then $(x,f(x)-\u03f5)\notin \mathrm{epi}f$, and since $f(x)>-\mathrm{\infty}$ we have $(x,f(x))\in \mathrm{epi}f$, and therefore
$(x,f(x))\in \mathrm{epi}f\cap \partial (\mathrm{epi}f)$.
We can now apply Lemma 6: $\mathrm{epi}f$ is a convex subset of the topological vector space $X\times \mathbb{R}$ with nonempty interior and $(x,f(x))\in \mathrm{epi}f\cap \partial (\mathrm{epi}f)$, so $\mathrm{epi}f$ is properly supported at $(x,f(x))$. That is, Lemma 6 shows that
there is some $\mathrm{\Lambda}\in {(X\times \mathbb{R})}^{*}$ such that

$$\mathrm{\Lambda}(x,f(x))=\underset{(y,\alpha )\in \mathrm{epi}f}{sup}\mathrm{\Lambda}(y,\alpha ),$$ |

and there is some $(y,\alpha )\in \mathrm{epi}f$ for which $\mathrm{\Lambda}(x,f(x))>\mathrm{\Lambda}(y,\alpha )$. Now, there is some $\lambda \in {X}^{*}$ and some $\beta \in {\mathbb{R}}^{*}=\mathbb{R}$ such that $\mathrm{\Lambda}(y,\alpha )=\lambda y+\beta \alpha $ for all $(y,\alpha )\in X\times \mathbb{R}$. Thus, there is some nonzero $\lambda \in {X}^{*}$ and some $\beta \in \mathbb{R}$ such that

$$\lambda x+\beta f(x)=\underset{(y,\alpha )\in \mathrm{epi}f}{sup}\lambda y+\beta \alpha .$$ |

If $\beta >0$ then the right-hand side would be $\mathrm{\infty}$ while the left-hand side is constant and $$, so $\beta \le 0$. Suppose by contradiction that $\beta =0$. Then $\lambda x\ge \lambda y$ for all $y\in \mathrm{dom}f$, and as $\lambda \ne 0$ this means that $x$ is a support point of $\mathrm{dom}f$, and then by Lemma 5 we have that $x\in \partial (\mathrm{dom}f)$, contradicting $x\in {(\mathrm{dom}f)}^{\circ}$. Hence $$, so

$$\lambda x+\beta f(x)\ge \lambda y+\beta f(y),y\in \mathrm{dom}f,$$ |

i.e.,

$$f(y)\ge f(x)-\frac{\lambda}{\beta}(y-x),y\in \mathrm{dom}f.$$ |

Furthermore, if $y\notin \mathrm{dom}f$ then $f(y)=\mathrm{\infty}$, for which the above inequality is true. Therefore, $f(y)\ge f(x)-\frac{\lambda}{\beta}(y-x)$ for all $y\in X$, showing that $-\frac{\lambda}{\beta}$ is a subgradient of $f$ at $x$. ∎

## 7 Directional derivatives

###### Lemma 8.

If $X$ is a vector space, $f\mathrm{:}X\mathrm{\to}\mathrm{(}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a proper convex function, $x\mathrm{\in}\mathrm{dom}\mathit{}f$, $v\mathrm{\in}X$, and $$, then

$$\frac{f(x+{h}^{\prime}v)-f(x)}{{h}^{\prime}}\le \frac{f(x+hv)-f(x)}{h}.$$ |

###### Proof.

We have

$$x+{h}^{\prime}v=\frac{{h}^{\prime}}{h}(x+hv)+\frac{h-{h}^{\prime}}{h}x,$$ |

and because $f$ is convex this gives

$$f(x+{h}^{\prime}v)\le \frac{{h}^{\prime}}{h}f(x+hv)+\frac{h-{h}^{\prime}}{h}f(x),$$ |

i.e.

$$f(x+{h}^{\prime}v)-f(x)\le \frac{{h}^{\prime}}{h}(f(x+hv)-f(x)).$$ |

Dividing by ${h}^{\prime}$,

$$\frac{f(x+{h}^{\prime}v)-f(x)}{{h}^{\prime}}\le \frac{f(x+hv)-f(x)}{h}.$$ |

∎

If $f:X\to (-\mathrm{\infty},\mathrm{\infty}]$ is a proper convex function, $x\in \mathrm{dom}f$, and $v\in X$, then the above lemma shows that

$$h\mapsto \frac{f(x+hv)-f(x)}{h}$$ |

is an increasing function $(0,\mathrm{\infty})\to (-\mathrm{\infty},\mathrm{\infty}]$, and therefore that

$$\underset{h\to {0}^{+}}{lim}\frac{f(x+hv)-f(x)}{h}$$ |

exists; it belongs to $[-\mathrm{\infty},\mathrm{\infty}]$, and if there is at least one $h>0$ for which $$ then the limit will be $$.
We define the one-sided directional derivative of $f$ at $x$ to be
the function ${d}^{+}f(x):X\to [-\mathrm{\infty},\mathrm{\infty}]$ defined by^{8}^{8}
8
We are following the notation of
Charalambos D. Aliprantis and Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker’s Guide, third ed., p. 266.

$${d}^{+}f(x)v=\underset{h\to {0}^{+}}{lim}\frac{f(x+hv)-f(x)}{h},v\in X.$$ |

###### Lemma 9.

If $X$ is a topological vector space, $f\mathrm{:}X\mathrm{\to}\mathrm{(}\mathrm{-}\mathrm{\infty}\mathrm{,}\mathrm{\infty}\mathrm{]}$ is a proper convex function, $x\mathrm{\in}{\mathrm{(}\mathrm{dom}\mathit{}f\mathrm{)}}^{\mathrm{\circ}}$, $f$ is continuous at $x$, and $v\mathrm{\in}X$, then $$.

###### Proof.

Because $x\in {(\mathrm{dom}f)}^{\circ}$, there is some $h>0$ for which $x+hv\in \mathrm{dom}f$ and hence for which $$. This implies that $$.

Let $h>0$. By Theorem 7, the subdifferential $\partial f(x)$ is nonempty, i.e. there is some $\lambda \in {X}^{*}$ for which $f(y)\ge f(x)+\lambda (y-x)$ for all $y\in X$. Thus, for all $v\in X$ we have, with $y=x+hv$,

$$f(x+hv)\ge f(x)+\lambda (hv),$$ |

i.e.,

$$\lambda v\le \frac{f(x+hv)-f(x)}{h}.$$ |

Since this difference quotient is bounded below by $\lambda v$, its limit as $h\to {0}^{+}$ is $>-\mathrm{\infty}$, and therefore ${d}^{+}f(x)v>-\mathrm{\infty}$. ∎