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

Let $n$ be a natural number with $1\le n$ and let $\mathbb{R}$ be the real numbers with the order $\le$ of their ordered field structure; $2$ denotes $1+1$, which satisfies $0<2$ and so has a multiplicative inverse by claim 8 of Elementary Order Arithmetic in an Ordered Field, and $\tfrac{a}{2}$ denotes the product of $a$ with that inverse. Regard Euclidean space $\mathbb{R}^{n}$ as a real vector space, with the sum of points, the scalar multiple, and the difference $y-x$ and dot product $p\cdot x$ of points; write $\lVert\,\cdot\,\rVert$ for the Euclidean norm and $d_{E}$ for the Euclidean distance, a metric on $\mathbb{R}^{n}$ with $d_{E}(x,y)=\lVert x-y\rVert$ by claim 2 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. Interiors are taken in the topological space formed by $\mathbb{R}^{n}$ and the open sets of $(\mathbb{R}^{n},d_{E})$, a topology by The Open Subsets of a Metric Space Form a Topology, in the sense of Interior of a Subset of a Topological Space.

Let $U\subseteq\mathbb{R}^{n}$ be convex, let $\mu\in\mathbb{R}$ satisfy $0\le\mu$, and let $\varphi:U\to\mathbb{R}$ be semiconvex on $U$ with constant $\mu$; thus the function $G:U\to\mathbb{R}$ given by

$$G(z)=\varphi(z)+\frac{\mu}{2}\,\lVert z\rVert^{2}$$

is convex on $U$, and its subdifferential relative to $U$ at a point $z$ is written $\partial_{U}G(z)$.

Let $A\subseteq U$, let $p\in\mathbb{R}^{n}$, and let $x\in A$ be an interior point of $A$ in $\mathbb{R}^{n}$ such that

$$\varphi(y)+p\cdot y\le\varphi(x)+p\cdot x\qquad\text{for every }y\in A .$$

Then the following hold.

1. (Subgradient) (i) $\mu x-p\in\partial_{U}G(x)$; that is,

$$G(y)\ge G(x)+(\mu x-p)\cdot(y-x)\qquad\text{for every }y\in U .$$

2. (Global quadratic lower bound) (ii) For every $y\in U$,

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