Subdifferentials of convex functions

1 Introduction

Whenever we speak about a vector space in this note we mean a vector space over $ℝ$. If $X$ is a topological vector space then we denote by $X^{*}$ the set of all continuous linear maps $X\to ℝ$. $X^{*}$ is called the dual space of $X$, and is itself a vector space.

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

$$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

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 ℝ:\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 ℝ$ 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 ℝ$.

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 ℝ$ 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 ℝ$ 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 ℝ$ 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 {ℝ}^X$ to converge to $f\in {ℝ}^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.

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 ℝ$ 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.

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 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 ℝ$ 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 ℝ$ 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.

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. 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 ℝ$, and is contained in $\mathrm{epi}f$. This shows that $\mathrm{epi}f$ has nonempty interior. Since , if $ϵ>0$ then $(x,f(x)-ϵ)\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 ℝ$ 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 ℝ)}^{*}$ 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 {ℝ}^{*}=ℝ$ such that $\mathrm{\Lambda }(y,\alpha )=\lambda y+\beta \alpha$ for all $(y,\alpha )\in X\times ℝ$. Thus, there is some nonzero $\lambda \in X^{*}$ and some $\beta \in ℝ$ 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

$$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 }$. ∎