Proof of The Subdifferential of a Convex Function on an Open Convex Set is Nonempty

We use the notation of the statement. Throughout we use Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space, by which $\iota$ is a linear bijection, and claim 3 of that lemma, by which

$$\iota(\xi,\eta)\cdot\iota(\xi',\eta')=\xi\cdot\xi'+\eta\,\eta'\qquad\text{and}\qquad\lVert\iota(\xi,\eta)\rVert^{2}=\lVert\xi\rVert^{2}+\eta^{2}$$

for $\xi,\xi'\in\mathbb{R}^{n}$ and $\eta,\eta'\in\mathbb{R}$. Algebraic manipulations of dot products use The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square.

Claim 1. Let $z\in U$. If $z=y$ the asserted inequality reads $f(y)\ge f(y)$, which holds. So assume $z\neq y$, and let $\theta$ be the smaller of $1$ and $r/\lVert z-y\rVert$, a real number with $0<\theta\le1$. Put $w=\theta z+(1-\theta)y=y+\theta(z-y)$, which lies in $U$ because $U$ is convex. By claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, $\lVert w-y\rVert=\theta\lVert z-y\rVert\le r$, so $w\in\bar{B}(y,r)$ and the hypothesis gives

$$f(w)\ge f(y)+p\cdot(w-y)=f(y)+\theta\,p\cdot(z-y).$$

On the other hand $f$ is convex on $U$, so $f(w)\le\theta f(z)+(1-\theta)f(y)$. Combining and subtracting $f(y)$,

$$\theta\,p\cdot(z-y)\le\theta\bigl(f(z)-f(y)\bigr),$$

and dividing by the positive number $\theta$ gives $f(z)\ge f(y)+p\cdot(z-y)$. As $z\in U$ was arbitrary, $p\in\partial_{U}f(y)$ by Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ (i).

Claim 2. Since $U$ is open, $y$ is an interior point of $U$, so A Convex Function is Lipschitz on a Ball around an Interior Point provides $r,M\in\mathbb{R}$ with $0<r$, $0\le M$, $\bar{B}(y,r)\subseteq U$ and

$$|f(z)-f(w)|\le M\,\lVert z-w\rVert\qquad\text{for all }z,w\in\bar{B}(y,r). \tag{L}$$

Put $c=f(y)+Mr+1$ and

$$K=\bigl\{\,\iota(z,t)\;:\;z\in\bar{B}(y,r),\ t\in\mathbb{R},\ f(z)\le t\ \text{ and }\ t\le c\,\bigr\}\subseteq\mathbb{R}^{n+1}.$$

$K$ is nonempty: $f(y)\le f(y)$ and $f(y)\le c$, so $\iota(y,f(y))\in K$.

$K$ is bounded: let $\iota(z,t)\in K$. Then $\lVert z\rVert\le\lVert y\rVert+r$ by claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, and by (L) $f(y)-Mr\le f(z)\le t\le c$, so $|t|\le|f(y)-Mr|+|c|$. Hence $\lVert\iota(z,t)\rVert^{2}=\lVert z\rVert^{2}+t^{2}$ is bounded above by a number independent of the point, and $K$ is bounded.

$K$ is closed: we use Sequential Characterization of Closed Subsets of a Metric Space. Let $(\xi_{m})_{m\in\mathbb{N}}$ be a sequence in $K$ converging to $\xi\in\mathbb{R}^{n+1}$. Since $\iota$ is a bijection we may write $\xi_{m}=\iota(z_{m},t_{m})$ and $\xi=\iota(z,t)$, and by linearity of $\iota$ and the norm identity,

$$\lVert\xi_{m}-\xi\rVert^{2}=\lVert\iota(z_{m}-z,t_{m}-t)\rVert^{2}=\lVert z_{m}-z\rVert^{2}+(t_{m}-t)^{2},$$

so $\lVert z_{m}-z\rVert\le\lVert\xi_{m}-\xi\rVert$ and $|t_{m}-t|\le\lVert\xi_{m}-\xi\rVert$; hence $(z_{m})$ converges to $z$ and $(t_{m})$ to $t$. The closed ball $\bar{B}(y,r)$ is closed by claim 3 of Elementary Properties of the Closed Ball in a Metric Space, so $z\in\bar{B}(y,r)$ by Sequential Characterization of Closed Subsets of a Metric Space again. From $t_{m}\le c$ and Order Properties of Limits of Real Sequences we get $t\le c$. Finally (L) gives $|f(z_{m})-f(z)|\le M\lVert z_{m}-z\rVert$, so $(f(z_{m}))$ converges to $f(z)$, and from $f(z_{m})\le t_{m}$ and Order Properties of Limits of Real Sequences we get $f(z)\le t$. Hence $\xi\in K$, and $K$ is closed.

$K$ is convex: let $\iota(z_{1},t_{1}),\iota(z_{2},t_{2})\in K$ and let $\theta\in\mathbb{R}$ with $0\le\theta\le1$. By linearity of $\iota$,

$$\theta\,\iota(z_{1},t_{1})+(1-\theta)\,\iota(z_{2},t_{2})=\iota\bigl(\theta z_{1}+(1-\theta)z_{2},\ \theta t_{1}+(1-\theta)t_{2}\bigr).$$

The point $\theta z_{1}+(1-\theta)z_{2}$ lies in $\bar{B}(y,r)$ by claim 2 of Euclidean Balls are Convex; the number $\theta t_{1}+(1-\theta)t_{2}$ is at most $c$; and since $f$ is convex on $U\supseteq\bar{B}(y,r)$,

$$f\bigl(\theta z_{1}+(1-\theta)z_{2}\bigr)\le\theta f(z_{1})+(1-\theta)f(z_{2})\le\theta t_{1}+(1-\theta)t_{2}.$$

Hence the combination lies in $K$.

Projections from below the graph. For $k\in\mathbb{N}$ put $\xi_{k}=\iota(y,f(y)-1/k)$. Since $\iota$ is injective, $\xi_{k}\in K$ would force $f(y)\le f(y)-1/k$, which is false; so $\xi_{k}\notin K$. By claim 1 of Nearest-Point Projection onto a Nonempty Closed Convex Subset of Euclidean Space, applied to the nonempty closed convex set $K$, the nearest point $\pi_{K}(\xi_{k})\in K$ is defined; write $\pi_{K}(\xi_{k})=\iota(z_{k},t_{k})$ and put $v_{k}=\xi_{k}-\pi_{K}(\xi_{k})$, which is nonzero because $\xi_{k}\notin K$ while $\pi_{K}(\xi_{k})\in K$. By claim 2 of that lemma, $v_{k}\cdot(w-\pi_{K}(\xi_{k}))\le0$ for every $w\in K$; multiplying by the positive number $1/\lVert v_{k}\rVert$ and putting $u_{k}=v_{k}/\lVert v_{k}\rVert$, a point with $\lVert u_{k}\rVert=1$ by claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, we get

$$u_{k}\cdot\bigl(w-\pi_{K}(\xi_{k})\bigr)\le0\qquad\text{for every }w\in K. \tag{N}$$

Since $\iota(y,f(y))\in K$, claims 3 and 4 of Nearest-Point Projection onto a Nonempty Closed Convex Subset of Euclidean Space give

$$\bigl\lVert\pi_{K}(\xi_{k})-\iota(y,f(y))\bigr\rVert=\bigl\lVert\pi_{K}(\xi_{k})-\pi_{K}(\iota(y,f(y)))\bigr\rVert\le\bigl\lVert\xi_{k}-\iota(y,f(y))\bigr\rVert=\lVert\iota(0,-1/k)\rVert=1/k,$$

and since by The Archimedean Property of the Real Numbers the numbers $1/k$ eventually fall below any prescribed positive real, the sequence $(\pi_{K}(\xi_{k}))_{k\in\mathbb{N}}$ converges to $\iota(y,f(y))$.

The points $u_{k}$ all lie in $\bar{B}(0,1)$, which is bounded, so The Bolzano-Weierstrass Theorem in $\mathbb{R}^n$ provides $u\in\mathbb{R}^{n+1}$ and a strictly increasing sequence $(p_{l})_{l\in\mathbb{N}}$ in $\mathbb{N}$ such that $(u_{p_{l}})_{l\in\mathbb{N}}$ converges to $u$. Choose $l_{0}$ with $\lVert u_{p_{l_{0}}}-u\rVert<1/2$; then by claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, $1=\lVert u_{p_{l_{0}}}\rVert\le\lVert u\rVert+\lVert u_{p_{l_{0}}}-u\rVert$, so $\lVert u\rVert\ge1/2$ and in particular $u\neq0$. Write $u=\iota(a,b)$ with $a\in\mathbb{R}^{n}$ and $b\in\mathbb{R}$.

Fix $w\in K$. For every $l$, by (N) and the dot product identity,

$$u_{p_{l}}\cdot\bigl(w-\pi_{K}(\xi_{p_{l}})\bigr)\le0 .$$

Both factors converge, the first to $u$ and the second to $w-\iota(y,f(y))$; since for any points $\alpha,\alpha',\beta,\beta'$ one has, by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and The Cauchy-Schwarz Inequality on $\mathbb{R}^n$,

$$|\alpha'\cdot\beta'-\alpha\cdot\beta|\le|(\alpha'-\alpha)\cdot\beta'|+|\alpha\cdot(\beta'-\beta)|\le\lVert\alpha'-\alpha\rVert\,\lVert\beta'\rVert+\lVert\alpha\rVert\,\lVert\beta'-\beta\rVert ,$$

and the norms $\lVert w-\pi_{K}(\xi_{p_{l}})\rVert$ are bounded, the left-hand sides converge to $u\cdot(w-\iota(y,f(y)))$. By Order Properties of Limits of Real Sequences, writing $w=\iota(z,t)$,

$$a\cdot(z-y)+b\,\bigl(t-f(y)\bigr)\le0\qquad\text{for every }\iota(z,t)\in K. \tag{H}$$

The last coordinate is negative. Taking $z=y$ and $t=f(y)+Mr+1=c$ in (H), which is legitimate since $f(y)\le c$, gives $b\,(Mr+1)\le0$, so $b\le0$ because $0<Mr+1$. Suppose $b=0$. Then $\lVert u\rVert^{2}=\lVert a\rVert^{2}$, so $a\neq0$. For $z\in\bar{B}(y,r)$ we have, by (L), $f(z)\le f(y)+M\lVert z-y\rVert\le f(y)+Mr<c$, so $\iota(z,f(z))\in K$ and (H) gives $a\cdot(z-y)\le0$. Taking $z=y+r\,a/\lVert a\rVert$, which lies in $\bar{B}(y,r)$ because $\lVert z-y\rVert=r$, we get $a\cdot(z-y)=r\,\lVert a\rVert^{2}/\lVert a\rVert=r\lVert a\rVert>0$, a contradiction. Hence $b<0$.

Conclusion. Put $p=(1/(-b))\,a$. For $z\in\bar{B}(y,r)$ we have $\iota(z,f(z))\in K$ as just shown, so (H) gives $a\cdot(z-y)+b(f(z)-f(y))\le0$, that is $a\cdot(z-y)\le(-b)\bigl(f(z)-f(y)\bigr)$. Dividing by the positive number $-b$ and using The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite,

$$f(z)\ge f(y)+p\cdot(z-y)\qquad\text{for every }z\in\bar{B}(y,r).$$

By claim 1, $p\in\partial_{U}f(y)$, so $\partial_{U}f(y)$ is nonempty.