Convex supports, localization, and the Lipschitz dual gradient

If $U$ is empty, all assertions are vacuous. If $n=0$ and $U$ is nonempty, then $U={\mathbb{R}}^0=\{0\}$, $\mathrm{\partial }f(0)=\{0\}$, and $f$ is differentiable with derivative zero. Every localization ball is $\{0\}$; set $H(0)=f(0)$. Then $F^{\ast }(0)=-f(0)$ and $g(0)=0$, so the remaining assertions hold directly. Henceforth assume $n\ge 1$. At $x\in U$, the directional slope $d(v)={\lim }_{t\downarrow 0}[f(x+tv)-f(x)]\mathrm{/}t$ exists and is finite: convexity makes these quotients monotone in $t$, while local Lipschitz continuity bounds them. Positive homogeneity follows by rescaling $t$. Convexity applied at the midpoint of $x+2tv$ and $x+2tw$ gives $d(v+w)\le d(v)+d(w)$. By [A1] and [F2], Hahn-Banach extends zero on $\{0\}$ to a linear functional $p\cdot v\le d(v)$. The chord inequality gives $d(y-x)\le f(y)-f(x)$, so $p\in \mathrm{\partial }f(x)$.

If $f$ is $L$-Lipschitz on a ball and $x$ lies in its concentric half ball, testing the support inequality at $x\pm te$ for every unit vector $e$ and sufficiently small $t>0$ gives $\mathrm{\mid }p\cdot e\mathrm{\mid }\le L$. Thus all its subgradients have norm at most $L$. On compact subsets this follows by a finite cover. If $x_j\to x$, $p_j\to p$, and $p_j\in \mathrm{\partial }f(x_j)$, pass to the limit in every support inequality using continuity of $f$; hence $p\in \mathrm{\partial }f(x)$. Differentiability gives $\mathrm{\partial }f(x)=\{Df(x)\}$ by testing both signs of small increments. Conversely, if $\mathrm{\partial }f(x)=\{p\}$, the local bound and [F3] imply that every choice $q_y\in \mathrm{\partial }f(y)$ converges to $p$ as $y\to x$: otherwise [A1] selects a contrary sequence with a convergent subsequence whose limit is a different limiting subgradient. The inequalities $p\cdot h\le f(x+h)-f(x)\le q_{x+h}\cdot h$ then prove differentiability with derivative $p$.

Set $H(z)=\sup \{f(x)+p\cdot (z-x):x\in K,p\in \mathrm{\partial }f(x)\}$. The local bounds from step 2.1 make slopes and intercepts uniformly bounded. Thus this supremum is finite, convex and globally Lipschitz; support inequalities give $H\le f$ on $U$, and the terms at $z=x\in K$ give equality on $K$. This definition uses all supports, without choosing one for each point.

Since $H$ is globally Lipschitz, $F(z)-p\cdot z\to +\mathrm{\infty }$ as $\mathrm{\mid }z\mathrm{\mid }\to \mathrm{\infty }$. Continuity and compact extreme values give a minimizer. The identity that $F-\mathrm{\mid }\cdot {\mathrm{\mid }}^2\mathrm{/}2$ is convex implies strict convexity of $F$ and uniqueness of this minimizer, denoted $g(p)$. Its minimizing property is exactly $p\in \mathrm{\partial }F(g(p))$. More precisely, $p\in \mathrm{\partial }F(x)$ iff $p-x\in \mathrm{\partial }H(x)$. One direction is immediate. For the other, test the support inequality for $F$ at $x+t(y-x)$, divide by $t>0$, and let $t\downarrow 0$; convexity makes the directional slope of $H$ at $x$ no larger than the full chord slope $H(y)-H(x)$, yielding $H(y)-H(x)\ge (p-x)\cdot (y-x)$. Monotonicity of supports of $H$, obtained by adding their two defining inequalities, therefore gives $(p-q)\cdot (g(p)-g(q))\ge \mathrm{\mid }g(p)-g(q){\mathrm{\mid }}^2$. Hence $g$ is one-Lipschitz.

The supremum defining $F^{\ast }(p)$ is finite and attained uniquely at $g(p)$. Evaluating the two suprema at each other's maximizers gives $0\le F^{\ast }(p+k)-F^{\ast }(p)-g(p)\cdot k\le (g(p+k)-g(p))\cdot k\le \mathrm{\mid }k{\mathrm{\mid }}^2$. This proves $D{F}^{\ast }=g$, whose continuity follows from its Lipschitz bound. It also proves the asserted subgradient inverse relation.