Proof of A Lipschitz Estimate Between the Maximisers of Two Linear Perturbations of a Semiconvex Function

Since $\bar{B}_{d_{E}}\bigl(\hat{x},\tfrac{r}{2}\bigr)\subseteq\bar{B}$, the point $x$ lies in $\bar{B}$, and $x'$ lies in $\bar{B}$ by hypothesis. Throughout we use the bilinearity and symmetry of the dot product (The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite), 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, and the fact that $2\lambda$ is positive and therefore invertible.

Step 1: $x$ is an interior point of $\bar{B}$. If $z\in\bar{B}_{d_{E}}\bigl(x,\tfrac{r}{2}\bigr)$ then, by the triangle inequality for the metric $d_{E}$,

$$d_{E}(\hat{x},z)\le d_{E}(\hat{x},x)+d_{E}(x,z)\le\frac{r}{2}+\frac{r}{2}=r,$$

so $\bar{B}_{d_{E}}\bigl(x,\tfrac{r}{2}\bigr)\subseteq\bar{B}$. By claim 2 of Interior Points in the Metric Topology are Exactly the Centres of Contained Closed Balls, $x$ is an interior point of $\bar{B}$ in $\mathbb{R}^{n}$.

Step 2: the global quadratic lower bound at $x$. The set $\bar{B}$ is convex by claim 1 of A Closed Euclidean Ball is Convex and Compact, and $\bar{B}\subseteq U$. Applying the global quadratic lower bound with the convex set $U$, the semiconvexity constant $\lambda$, the subset $A=\bar{B}$, the interior point $x$ of step 1 and the vector $p$, we obtain

$$\varphi(y)\ \ge\ \varphi(x)-p\cdot(y-x)-\frac{\lambda}{2}\,\lVert y-x\rVert^{2}\qquad\text{for every }y\in U . \tag{L}$$

Step 3: a good test point. Put $w=\lambda^{-1}(p'-p)$ and $y=x+w$. 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 and the hypothesis $\lVert p-p'\rVert\le\lambda r/2$,

$$\lVert w\rVert=\lambda^{-1}\lVert p'-p\rVert=\lambda^{-1}\lVert p-p'\rVert\le\frac{r}{2},$$

so $d_{E}(\hat{x},y)\le d_{E}(\hat{x},x)+d_{E}(x,y)\le\tfrac{r}{2}+\tfrac{r}{2}=r$ and hence $y\in\bar{B}\subseteq U$.

Step 4: evaluating the two inequalities at $y$. Since $y-x=w$, we have $\lVert y-x\rVert^{2}=\lambda^{-2}\lVert p-p'\rVert^{2}$ and $p\cdot(y-x)=\lambda^{-1}\,p\cdot(p'-p)$, so (L) at this $y$ reads

$$\varphi(y)\ \ge\ \varphi(x)-\lambda^{-1}\,p\cdot(p'-p)-\frac{1}{2\lambda}\,\lVert p-p'\rVert^{2}.$$

On the other hand $y\in\bar{B}$, so the maximum property of $x'$ gives $\varphi(y)+p'\cdot y\le\varphi(x')+p'\cdot x'$, that is, using $y-x'=(x-x')+w$,

$$\varphi(y)\ \le\ \varphi(x')-p'\cdot(y-x')=\varphi(x')-p'\cdot(x-x')-\lambda^{-1}\,p'\cdot(p'-p).$$

Combining the two displays and rearranging,

$$\varphi(x)-\varphi(x')\ \le\ -p'\cdot(x-x')+\lambda^{-1}\,(p-p')\cdot(p'-p)+\frac{1}{2\lambda}\,\lVert p-p'\rVert^{2}.$$

Now $(p-p')\cdot(p'-p)=-(p-p')\cdot(p-p')=-\lVert p-p'\rVert^{2}$, so the right-hand side equals

$$-p'\cdot(x-x')-\frac{1}{\lambda}\lVert p-p'\rVert^{2}+\frac{1}{2\lambda}\lVert p-p'\rVert^{2}=-p'\cdot(x-x')-\frac{1}{2\lambda}\,\lVert p-p'\rVert^{2},$$

and therefore

$$\varphi(x)-\varphi(x')\ \le\ -p'\cdot(x-x')-\frac{1}{2\lambda}\,\lVert p-p'\rVert^{2}. \tag{A}$$

Step 5: proof of claim 1. Since $x'\in\bar{B}$, the maximum property of $x$ gives $\varphi(x')+p\cdot x'\le\varphi(x)+p\cdot x$, that is,

$$\varphi(x')-\varphi(x)\ \le\ p\cdot(x-x'). \tag{B}$$

Adding (A) and (B),

$$0\ \le\ (p-p')\cdot(x-x')-\frac{1}{2\lambda}\,\lVert p-p'\rVert^{2},$$

and multiplying by the positive number $2\lambda$ gives

$$\lVert p-p'\rVert^{2}\ \le\ 2\lambda\,(p-p')\cdot(x-x'),$$

which is claim 1.

Step 6: proof of claim 2. By The Cauchy-Schwarz Inequality on $\mathbb{R}^n$,

$$(p-p')\cdot(x-x')\le\bigl|(p-p')\cdot(x-x')\bigr|\le\lVert p-p'\rVert\,\lVert x-x'\rVert ,$$

so claim 1 yields

$$\lVert p-p'\rVert^{2}\ \le\ 2\lambda\,\lVert p-p'\rVert\,\lVert x-x'\rVert .$$

If $\lVert p-p'\rVert=0$ then, since $0\le 2\lambda\lVert x-x'\rVert$, the inequality $\lVert p-p'\rVert\le 2\lambda\lVert x-x'\rVert$ holds. Otherwise $0<\lVert p-p'\rVert$ and dividing the last display by $\lVert p-p'\rVert$ gives the same inequality. This is the first assertion of claim 2.

Finally, if $x=x'$ then $x-x'$ is the origin and $\lVert x-x'\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, so $\lVert p-p'\rVert\le 0$; as norms are nonnegative, $\lVert p-p'\rVert=0$ and hence $p-p'$ is the origin by claim 3 there, that is, $p=p'$.