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

$$\bar{B}_{d_{E}}(x,\sigma)\subseteq A ,$$

closed balls being those of Closed Ball in a Metric Space. Throughout we use the bilinearity and symmetry of the dot product (The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite) and the identity $\lVert z\rVert^{2}=z\cdot z$ of 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.

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square.

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

$$d_{E}(x,z_{t})=\lVert z_{t}-x\rVert=\lVert(-t)\,v\rVert=t\,\lVert v\rVert\le\sigma$$

by claims 2 and 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, 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

$$\frac{t}{1+t}\,y+\frac{1}{1+t}\,z_{t}=\frac{t\,y+x-t\,(y-x)}{1+t}=\frac{x+t\,x}{1+t}=x .$$

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

$$G(x)\le\frac{t}{1+t}\,G(y)+\frac{1}{1+t}\,G(z_{t}).$$

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

$$t\,G(y)\ \ge\ (1+t)\,G(x)-G(z_{t})\ =\ t\,G(x)+\bigl(G(x)-G(z_{t})\bigr). \tag{$\ast$}$$

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,

$$\varphi(z_{t})\le\varphi(x)+p\cdot(x-z_{t})=\varphi(x)+t\,(p\cdot v).$$

Moreover

$$\lVert z_{t}\rVert^{2}=(x-t\,v)\cdot(x-t\,v)=\lVert x\rVert^{2}-2t\,(x\cdot v)+t^{2}\,\lVert v\rVert^{2},$$

so that

$$\frac{\mu}{2}\bigl(\lVert x\rVert^{2}-\lVert z_{t}\rVert^{2}\bigr)=\mu\,t\,(x\cdot v)-\frac{\mu\,t^{2}}{2}\,\lVert v\rVert^{2}.$$

Adding the two displays,

$$G(x)-G(z_{t})=\bigl(\varphi(x)-\varphi(z_{t})\bigr)+\frac{\mu}{2}\bigl(\lVert x\rVert^{2}-\lVert z_{t}\rVert^{2}\bigr)\ \ge\ t\,\bigl((\mu\,x-p)\cdot v\bigr)-\frac{\mu\,t^{2}}{2}\,\lVert v\rVert^{2}.$$

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

$$G(y)\ \ge\ G(x)+(\mu\,x-p)\cdot v-\frac{\mu\,t}{2}\,\lVert v\rVert^{2}.$$

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

$$D\ \ge\ -C\,t\qquad\text{for every real }t\text{ with }0<t\le\frac{\sigma}{\lVert v\rVert}.$$

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,

$$G(y)\ \ge\ G(x)+(\mu\,x-p)\cdot(y-x).$$

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

$$\frac{\mu}{2}\bigl(\lVert x\rVert^{2}-\lVert y\rVert^{2}\bigr)=-\mu\,(x\cdot v)-\frac{\mu}{2}\,\lVert v\rVert^{2}.$$

By claim 1,

$$\varphi(y)+\frac{\mu}{2}\lVert y\rVert^{2}\ \ge\ \varphi(x)+\frac{\mu}{2}\lVert x\rVert^{2}+(\mu\,x-p)\cdot v ,$$

hence

$$\varphi(y)\ \ge\ \varphi(x)+\frac{\mu}{2}\bigl(\lVert x\rVert^{2}-\lVert y\rVert^{2}\bigr)+\mu\,(x\cdot v)-p\cdot v\ =\ \varphi(x)-p\cdot(y-x)-\frac{\mu}{2}\,\lVert y-x\rVert^{2},$$

which is claim 2.