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

for $\xi,\xi'\in\mathbb{R}^{n}$ and $\eta,\eta'\in\mathbb{R}$. Algebraic manipulations of dot products use Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $\lVert w-y\rVert=\theta\lVert z-y\rVert\le r$, so $w\in\bar{B}(y,r)$ and the hypothesis gives

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

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$ §subdifferential.

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

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

$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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, 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,

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

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

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, we get

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

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 Bolzano-Weierstrass Theorem in Euclidean Space 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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $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,

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 Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and Cauchy-Schwarz Inequality for the Euclidean Dot Product,

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

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 Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$,

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