Proof of Elementary Calculus of the Subdifferential of a Convex Function

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

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 Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$. So assume $q\neq0$ and put $z=y+r\,q/\lVert q\rVert$. By claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $\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

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

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

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

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

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 Bolzano-Weierstrass Theorem in Euclidean Space 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.