Proof of Elementary Calculus of the Subdifferential of a Convex Function

We use the notation of the statement. 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. Membership in a subdifferential always refers to Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ (i).

Claim 1. By hypothesis $f(y')\ge f(y)+q\cdot(y'-y)$ and $f(y)\ge f(y')+q'\cdot(y-y')$. Adding these and cancelling $f(y)+f(y')$ gives $0\ge q\cdot(y'-y)+q'\cdot(y-y')$. Since $q\cdot(y'-y)=-q\cdot(y-y')$, the right-hand side equals $-(q-q')\cdot(y-y')$, so $0\le(q-q')\cdot(y-y')$.

Claim 2. Let $y\in\bar{B}(y_{0},r)$ and $q\in\partial_{U}f(y)$. If $q=0$ then $\lVert q\rVert=0\le M$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. So assume $q\neq0$ and put $z=y+r\,q/\lVert q\rVert$. 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 z-y\rVert=r$, so by claim 6 of that lemma $\lVert z-y_{0}\rVert\le\lVert z-y\rVert+\lVert y-y_{0}\rVert\le r+r=2r$ and hence $z\in\bar{B}(y_{0},2r)\subseteq U$. The subgradient inequality at $y$ gives

$$f(z)-f(y)\ge q\cdot(z-y)=r\,\frac{q\cdot q}{\lVert q\rVert}=r\,\lVert q\rVert ,$$

while the Lipschitz hypothesis, applicable because $y,z\in\bar{B}(y_{0},2r)$, gives $f(z)-f(y)\le M\lVert z-y\rVert=Mr$. Hence $r\lVert q\rVert\le Mr$, and dividing by the positive number $r$ gives $\lVert q\rVert\le M$.

Claim 3. 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 $\rho,L\in\mathbb{R}$ with $0<\rho$, $0\le L$, $\bar{B}(y,\rho)\subseteq U$ and $|f(w)-f(w')|\le L\lVert w-w'\rVert$ for $w,w'\in\bar{B}(y,\rho)$. As $(y_{m})$ converges to $y$ there is $m_{0}$ with $\lVert y_{m}-y\rVert\le\rho$ for $m\ge m_{0}$, and then $|f(y_{m})-f(y)|\le L\lVert y_{m}-y\rVert$, so $(f(y_{m}))_{m\in\mathbb{N}}$ converges to $f(y)$.

Fix $z\in U$. For every $m$ the subgradient inequality gives $f(z)\ge f(y_{m})+q_{m}\cdot(z-y_{m})$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite and The Cauchy-Schwarz Inequality on $\mathbb{R}^n$,

$$\bigl|q_{m}\cdot(z-y_{m})-q\cdot(z-y)\bigr|\le\lVert q_{m}-q\rVert\,\lVert z-y_{m}\rVert+\lVert q\rVert\,\lVert y-y_{m}\rVert ,$$

and the norms $\lVert z-y_{m}\rVert$ are bounded because $(y_{m})$ converges, so $(q_{m}\cdot(z-y_{m}))_{m\in\mathbb{N}}$ converges to $q\cdot(z-y)$. By Arithmetic of Limits of Real Sequences the right-hand sides converge to $f(y)+q\cdot(z-y)$, and by Order Properties of Limits of Real Sequences applied to the constant sequence with value $f(z)$ we get $f(z)\ge f(y)+q\cdot(z-y)$. As $z\in U$ was arbitrary, $q\in\partial_{U}f(y)$.

Claim 4. We first show $g\in\partial_{U}f(y)$. Let $z\in U$ and put $h=z-y$; if $h=0$ the required inequality is an equality, so assume $h\neq0$. Let $\varepsilon\in\mathbb{R}$ with $0<\varepsilon$, and let $\delta>0$ be as in Differentiability at a Point for Functions Between Euclidean Spaces for this $\varepsilon$, so that $|f(y+k)-f(y)-g\cdot k|\le\varepsilon\lVert k\rVert$ whenever $0<\lVert k\rVert<\delta$; here we used that the single coordinate of $Ak$ is $g\cdot k$ and that the Euclidean norm of a point of $\mathbb{R}^{1}$ is the absolute value of its coordinate, both being the unique nonnegative real number whose square is the square of that coordinate, by 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. Choose $\theta\in\mathbb{R}$ with $0<\theta\le1$ and $\theta\lVert h\rVert<\delta$. The point $y+\theta h=\theta z+(1-\theta)y$ lies in $U$ because $U$ is convex, and by convexity of $f$,

$$f(y+\theta h)\le\theta f(z)+(1-\theta)f(y),\qquad\text{that is}\qquad \frac{f(y+\theta h)-f(y)}{\theta}\le f(z)-f(y).$$

Taking $k=\theta h$ in the differentiability estimate gives $|f(y+\theta h)-f(y)-\theta\,g\cdot h|\le\varepsilon\theta\lVert h\rVert$, so after dividing by $\theta$,

$$g\cdot h-\varepsilon\lVert h\rVert\le\frac{f(y+\theta h)-f(y)}{\theta}\le f(z)-f(y).$$

As $\varepsilon>0$ was arbitrary, $g\cdot h\le f(z)-f(y)$, that is $f(z)\ge f(y)+g\cdot(z-y)$. Hence $g\in\partial_{U}f(y)$.

Now let $q\in\partial_{U}f(y)$ and let $\varepsilon>0$. For this $\varepsilon$ let $\delta>0$ be as supplied by Differentiability at a Point for Functions Between Euclidean Spaces in the paragraph above, shrunk if necessary so that also $\lVert k\rVert<\delta$ implies $y+k\in U$, which is possible because $U$ is open. Suppose $q\neq g$ and put $k=\tfrac{1}{2}\delta\,(q-g)/\lVert q-g\rVert$, so that $0<\lVert k\rVert=\tfrac{1}{2}\delta<\delta$. From $q\in\partial_{U}f(y)$ we get $f(y+k)-f(y)\ge q\cdot k$, and from differentiability $f(y+k)-f(y)\le g\cdot k+\varepsilon\lVert k\rVert$. Hence $(q-g)\cdot k\le\varepsilon\lVert k\rVert$, that is $\tfrac{1}{2}\delta\,\lVert q-g\rVert\le\varepsilon\,\tfrac{1}{2}\delta$, so $\lVert q-g\rVert\le\varepsilon$. This holds for every $\varepsilon>0$, so $\lVert q-g\rVert=0$ and $q=g$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. Therefore $\partial_{U}f(y)=\{g\}$.

Claim 5. Since $U$ is open, A Convex Function is Lipschitz on a Ball around an Interior Point provides $\rho,L\in\mathbb{R}$ with $0<\rho$, $0\le L$, $\bar{B}(y,\rho)\subseteq U$ and $|f(w)-f(w')|\le L\lVert w-w'\rVert$ for $w,w'\in\bar{B}(y,\rho)$. Put $r=\rho/2$; then $\bar{B}(y,2r)=\bar{B}(y,\rho)\subseteq U$, so by claim 2, applied with $y_{0}=y$ and the constant $L$,

$$\lVert q'\rVert\le L\qquad\text{for every }y'\in\bar{B}(y,r)\text{ and every }q'\in\partial_{U}f(y'). \tag{B}$$

Let $\varepsilon>0$ and suppose, for contradiction, that no $\delta>0$ has the asserted property. Then for every $m\in\mathbb{N}$, applying this to the positive number which is the smaller of $r$ and $1/m$, there are $y_{m}\in U$ with $\lVert y_{m}-y\rVert<\min\{r,1/m\}$ and $q_{m}\in\partial_{U}f(y_{m})$ with $\lVert q_{m}-p\rVert\ge\varepsilon$. Since by The Archimedean Property of the Real Numbers the numbers $1/m$ eventually fall below any prescribed positive real, the sequence $(y_{m})$ converges to $y$; and by (B) every $q_{m}$ lies in $\bar{B}(0,L)$, which is bounded. By The Bolzano-Weierstrass Theorem in $\mathbb{R}^n$ there are $q\in\mathbb{R}^{n}$ and a strictly increasing sequence $(p_{l})_{l\in\mathbb{N}}$ in $\mathbb{N}$ with $(q_{p_{l}})_{l\in\mathbb{N}}$ converging to $q$. The sequence $(y_{p_{l}})_{l\in\mathbb{N}}$ converges to $y$, so claim 3 gives $q\in\partial_{U}f(y)=\{p\}$, that is $q=p$. But then $\lVert q_{p_{l}}-p\rVert$ converges to $0$, contradicting $\lVert q_{p_{l}}-p\rVert\ge\varepsilon$ for every $l$. Hence some $\delta>0$ has the asserted property.