Proof of A Maximiser of a Linearly Perturbed Semiconvex Function Yields a Subgradient and a Global Quadratic Lower Bound

Since $x$ is an interior point of $A$ in $\mathbb{R}^{n}$, claim 1 of Interior Points in the Metric Topology are Exactly the Centres of Contained Closed Balls supplies $\sigma\in\mathbb{R}$ with $0<\sigma$ and

closed balls being those of Closed Ball in a Metric Space. Throughout we use the bilinearity and symmetry of the dot product (Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$) and the identity $\lVert z\rVert^{2}=z\cdot z$ of claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

Proof of claim 1. Let $y\in U$. If $y=x$ the asserted inequality reads $G(x)\ge G(x)$ and holds, so assume $y\ne x$ and put $v=y-x$; then $\lVert v\rVert>0$ by claim 3 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$.

Let $t\in\mathbb{R}$ satisfy $0<t$ and $t\,\lVert v\rVert\le\sigma$, and put $z_{t}=x-t\,v$. Then

by claims 2 and 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, so $z_{t}\in\bar{B}_{d_{E}}(x,\sigma)\subseteq A\subseteq U$.

The real numbers $\tfrac{t}{1+t}$ and $\tfrac{1}{1+t}$ are nonnegative and sum to $1$, and

Since $U$ is convex and $y,z_{t}\in U$, convexity of $G$ on $U$ (Convex Real-Valued Function on a Convex Subset of $\mathbb{R}^n$, applied with the coefficient $\tfrac{t}{1+t}$, which lies between $0$ and $1$) gives

Multiplying by the positive number $1+t$ and rearranging,

We bound $G(x)-G(z_{t})$ from below. As $z_{t}\in A$, the maximum hypothesis gives $\varphi(z_{t})+p\cdot z_{t}\le\varphi(x)+p\cdot x$, that is,

Moreover

so that

Adding the two displays,

Substituting this into $(\ast)$ and dividing by $t>0$,

Put $D=G(y)-G(x)-(\mu\,x-p)\cdot v$ and $C=\tfrac{\mu}{2}\lVert v\rVert^{2}$, so that $0\le C$ and

Suppose $D<0$. If $C=0$ then taking $t=\sigma/\lVert v\rVert$ gives $D\ge 0$, a contradiction. If $0<C$, choose a real $t$ with $0<t$, $t\le\sigma/\lVert v\rVert$ and $t<-D/C$ (the smaller of $\sigma/\lVert v\rVert$ and half of $-D/C$ will do, both being positive); then $-C\,t>D$, contradicting the display. Hence $0\le D$, that is,

As $y\in U$ was arbitrary, $\mu\,x-p\in\partial_{U}G(x)$ by Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$. This proves claim 1.

Proof of claim 2. Let $y\in U$ and put $v=y-x$. Expanding as above, $\lVert y\rVert^{2}=(x+v)\cdot(x+v)=\lVert x\rVert^{2}+2\,(x\cdot v)+\lVert v\rVert^{2}$, so

By claim 1,

hence

which is claim 2.