Proof of A Convex Function on a Convex Subset of $\mathbb{R}^n$ Has a Subgradient at Every Interior Point

Let $E=\operatorname{epi}f\subseteq\mathbb{R}^{n+1}$ be the epigraph of $f$ (Epigraph of a Real-Valued Function on a Subset of $\mathbb{R}^n$ (i)) and $p=(x,f(x))$. Throughout, pairs are added, scaled, paired by the dot product and measured as in Convex Functions on $\mathbb{R}^n$: Standing Notation (ii), and a point of $\mathbb{R}^{n+1}$ determines its pair uniquely.

By A Function on a Convex Subset of $\mathbb{R}^n$ Is Convex If and Only If Its Epigraph Is Convex (i), $E$ is a convex subset of $\mathbb{R}^{n+1}$. Moreover $p$ is not an interior point of $E$. Indeed, let $r>0$ and $q=(x,f(x)-r/2)$. Then $q-p=(0,-r/2)$, so

$$d_{E}(p,q)=\lVert q-p\rVert=r/2<r$$

(Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (ii), with $n+1$ in place of $n$), and $q\in B(p,r)$ in $\mathbb{R}^{n+1}$ (Open Ball in a Metric Space (ii)). But $q\notin E$, since its second entry $f(x)-r/2$ is less than $f(x)$. So no open ball about $p$ lies in $E$, and $p\notin\operatorname{int}E$ by Interior of a Subset of a Metric Space (ii).

By The Supporting Hyperplane Theorem in $\mathbb{R}^n$ (i), with $n+1$ in place of $n$, applied to $E$ and $p$, there is $w\in\mathbb{S}$ (so $\lVert w\rVert=1$) with $w\cdot e\le w\cdot p$ for every $e\in E$. Write $w=(b,\beta)$ with $b\in\mathbb{R}^{n}$ and $\beta\in\mathbb{R}$. Then $\lVert b\rVert^{2}+\beta^{2}=1$ and

$$b\cdot y+\beta\mu\le b\cdot x+\beta f(x)\qquad\text{for every }(y,\mu)\in E. \tag{1}$$

We show that $\beta<0$. The point $(x,f(x)+1)$ lies in $E$, and (1) gives $\beta(f(x)+1)\le\beta f(x)$, that is, $\beta\le0$. Suppose that $\beta=0$. Then $\lVert b\rVert=1$, and (1) with $\mu=f(y)$ gives $b\cdot y\le b\cdot x$ for every $y\in C$. Since $x$ is an interior point of $C$, Interior of a Subset of a Metric Space (i) gives a real $\rho>0$ with $B(x,\rho)\subseteq C$. The point $y=x+(\rho/2)b$ satisfies $d_{E}(x,y)=(\rho/2)\lVert b\rVert=\rho/2<\rho$ (Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (ii), Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (v)), so $y\in C$; but

$$b\cdot y=b\cdot x+(\rho/2)\lVert b\rVert^{2}=b\cdot x+\rho/2>b\cdot x,$$

a contradiction. Hence $\beta<0$.

Finally let $a=(-1/\beta)\,b$. For $y\in C$ the point $(y,f(y))$ lies in $E$, and (1) gives $\beta\bigl(f(y)-f(x)\bigr)\le-\,b\cdot(y-x)$. Dividing by $-\beta>0$,

$$f(y)\ge f(x)+a\cdot(y-x)\qquad\text{for every }y\in C.$$

So $a$ is a subgradient of $f$ at $x$, hence $a\in\partial f(x)$ by Subgradients and the Subdifferential of a Real-Valued Function on a Subset of $\mathbb{R}^n$ (ii), and $\partial f(x)\neq\emptyset$.