Proof of Basic Properties of the Legendre-Fenchel Conjugate: the Fenchel-Young Inequality, Convexity, Full Domain under Superlinear Growth, and the Quadratic

Each result cited is universally quantified over the data in its own statement. Elementary arithmetic and order facts in $\mathbb{R}$ and the properties of $|\cdot|$ are those put in force by The Real Numbers: Standing Notation and Background §background; upper bounds and least upper bounds are those of The Real Numbers: Standing Notation and Background §bounds. For $p\in D(f^{*})$, $f^{*}(p)$ is by The Legendre-Fenchel Conjugate of a Real Function on a Subset of Euclidean Space §conjugate the least upper bound of $\{p\cdot x-f(x):x\in C\}$, so

Sums and scalar multiples of points of $\mathbb{R}^{n}$ are those of that definition and that definition, and the dot product is bilinear and symmetric by Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$.

Claim 1. Adding $f(x)$ to both sides of the first inequality in ($*$) gives $p\cdot x\le f(x)+f^{*}(p)$.

Claim 2. Let $p,q\in D(f^{*})$, let $t\in\mathbb{R}$ with $0\le t\le1$, and put $r=tp+(1-t)q$. For $x\in C$, claims 2 and 4 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ give $r\cdot x=t\,(p\cdot x)+(1-t)\,(q\cdot x)$, and $f(x)=t\,f(x)+(1-t)\,f(x)$, so

by ($*$) for $p$ and for $q$, multiplied by the nonnegative numbers $t$ and $1-t$. Hence $x\mapsto r\cdot x-f(x)$ is bounded above on $C$, that is, $r\in D(f^{*})$ by The Legendre-Fenchel Conjugate of a Real Function on a Subset of Euclidean Space §domain, so $D(f^{*})$ is convex; and the second part of ($*$) gives $f^{*}(r)\le t\,f^{*}(p)+(1-t)\,f^{*}(q)$, so $f^{*}$ is convex on $D(f^{*})$.

Claim 3. Let $p\in\mathbb{R}^{n}$ and $R=\lVert p\rVert+1$, which is positive because $0\le\lVert p\rVert$ by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$. For $x\in C$, $p\cdot x\le|p\cdot x|\le\lVert p\rVert\,\lVert x\rVert$ by claim 3 of Properties of the Absolute Value in an Ordered Field and Cauchy-Schwarz Inequality for the Euclidean Dot Product, while $-f(x)\le c_{R}-R\lVert x\rVert$ by hypothesis; adding,

So $x\mapsto p\cdot x-f(x)$ is bounded above on $C$, and $p\in D(f^{*})$ by The Legendre-Fenchel Conjugate of a Real Function on a Subset of Euclidean Space §domain. As $p$ was arbitrary, $D(f^{*})=\mathbb{R}^{n}$.

Claim 4. Let $C=\mathbb{R}^{n}$, $f(x)=\tfrac12\lVert x\rVert^{2}$, and $p,x\in\mathbb{R}^{n}$. By claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $\lVert y\rVert^{2}=y\cdot y$ for every $y$, so claims 1, 3 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ give

and therefore

since $0\le\lVert x-p\rVert^{2}$, a product of two nonnegative numbers. So $p\in D(f^{*})$ by The Legendre-Fenchel Conjugate of a Real Function on a Subset of Euclidean Space §domain, whence $D(f^{*})=\mathbb{R}^{n}$, and $f^{*}(p)\le\tfrac12\lVert p\rVert^{2}$ by ($*$). Taking $x=p$, and using $p\cdot p=\lVert p\rVert^{2}$, gives $p\cdot p-\tfrac12\lVert p\rVert^{2}=\tfrac12\lVert p\rVert^{2}$, which is at most $f^{*}(p)$ by ($*$). Hence $f^{*}(p)=\tfrac12\lVert p\rVert^{2}$.