Proof of Rockafellar's Theorem: a Cyclically Monotone Set Lies in the Subdifferential of a Convex Function

Each result cited below is universally quantified over the data in its own statement. Finite sums of real numbers are those of Finite Sum Notation in a Field.

Since $\Gamma\ne\emptyset$, fix $\hat z\in\Gamma$ and write $\hat x=\mathrm{pr}_{1}(\hat z)$ and $\hat y=\mathrm{pr}_{2}(\hat z)$.

1. Chains and their values. Call chain a pair $\gamma=(n,(z_{1},\dots,z_{n}))$ consisting of $n\in\mathbb{N}$ and points $z_{1},\dots,z_{n}\in\Gamma$ with $z_{1}=\hat z$; write $x_{i}=\mathrm{pr}_{1}(z_{i})$ and $y_{i}=\mathrm{pr}_{2}(z_{i})$ for $i\in[n]$. Chains exist: $(1,(\hat z))$ is one. For $u\in\mathbb{R}^{d}$ define the points $w^{u}_{i}=x_{i}$ for $i\in[n]$ and $w^{u}_{n+1}=u$, and put

$$V_{\gamma}(u)=\sum_{i=1}^{n}y_{i}\cdot\bigl(w^{u}_{i+1}-w^{u}_{i}\bigr).$$

By the recursion of claim 1 of Properties of Finite Sums, $V_{\gamma}(u)=y_{1}\cdot(u-x_{1})$ if $n=1$, and

$$V_{\gamma}(u)=\Bigl(\sum_{i=1}^{n-1}y_{i}\cdot(x_{i+1}-x_{i})\Bigr)+y_{n}\cdot(u-x_{n})\qquad\text{if }2\le n ,$$

these two cases being exhaustive by claims 3 and 4 of Properties of the Order on the Natural Numbers. In both cases bilinearity of the dot product (The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite) gives a real number $c_{\gamma}$, not depending on $u$, with

$$V_{\gamma}(u)=y_{n}\cdot u+c_{\gamma}\qquad\text{for every }u\in\mathbb{R}^{d}.$$

2. The domain and the potential. Let $S(u)=\{V_{\gamma}(u):\gamma\text{ a chain}\}$, a nonempty set of real numbers, and let $C$ be the set of those $u\in\mathbb{R}^{d}$ for which $S(u)$ has an upper bound in $\mathbb{R}$. $C$ is convex: let $u,u'\in C$, let $\phi(u)$ and $\phi(u')$ be upper bounds of $S(u)$ and $S(u')$, and let $t\in\mathbb{R}$ with $0\le t\le1$. For every chain $\gamma$, step 1 and $t+(1-t)=1$ give

$$V_{\gamma}\bigl(tu+(1-t)u'\bigr)=t\,V_{\gamma}(u)+(1-t)\,V_{\gamma}(u')\le t\,\phi(u)+(1-t)\,\phi(u'),$$

by claim 5 of Elementary Arithmetic in an Ordered Field (multiplication by the nonnegative numbers $t$ and $1-t$) and claims 2 and 3 of that lemma (addition of two inequalities, each rewritten as the nonnegativity of a difference); so $tu+(1-t)u'\in C$.

Each $V_{\gamma}$, restricted to $C$, is convex on $C$ by claim 1 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions, being affine by step 1. Since $S(u)$ is bounded above for every $u\in C$, claim 4 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions shows that the function $\phi:C\to\mathbb{R}$ whose value at $u$ is the least upper bound of $S(u)$ is well defined and convex on $C$.

3. $\hat x\in C$ and $\phi(\hat x)=0$. Let $\gamma=(n,(z_{1},\dots,z_{n}))$ be a chain. Then $V_{\gamma}(\hat x)$ is the sum $\sum_{i=1}^{n}y_{i}\cdot(w_{i+1}-w_{i})$ with $w_{i}=x_{i}$ for $i\in[n]$ and $w_{n+1}=\hat x=x_{1}$; this is exactly the sum which Cyclically Monotone Subset of a Doubled Euclidean Space (i) requires to be nonpositive, read with $N=n$ and the points $z_{1},\dots,z_{n}$ of $\Gamma$. Hence $V_{\gamma}(\hat x)\le0$, so $S(\hat x)$ is bounded above by $0$ and $\hat x\in C$. The chain $(1,(\hat z))$ gives $V(\hat x)=\hat y\cdot(\hat x-\hat x)=0$ by bilinearity of the dot product, so $0\in S(\hat x)$ and $\phi(\hat x)=0$. In particular $C\ne\emptyset$.

4. Claim 1. Let $z\in\Gamma$ and put $x=\mathrm{pr}_{1}(z)$, $y=\mathrm{pr}_{2}(z)$. Let $\gamma=(n,(z_{1},\dots,z_{n}))$ be a chain and consider the $n+1$ points $z_{1},\dots,z_{n},z_{n+1}=z$ of $\Gamma$. Applying Cyclically Monotone Subset of a Doubled Euclidean Space (i) with $N=n+1$ to these points, and splitting off the last summand by claim 1 of Properties of Finite Sums, gives

$$V_{\gamma}(x)+y\cdot(\hat x-x)=\sum_{i=1}^{n+1}y_{i}\cdot(x_{i+1}-x_{i})\le0 ,$$

where the indexing of that definition sets $x_{n+2}=x_{1}=\hat x$, and where the first $n$ summands are precisely those of $V_{\gamma}(x)$ because $x_{n+1}=\mathrm{pr}_{1}(z)=x$. By bilinearity of the dot product, $-\bigl(y\cdot(\hat x-x)\bigr)=y\cdot(x-\hat x)$, so $V_{\gamma}(x)\le y\cdot(x-\hat x)$. The right-hand side does not depend on $\gamma$, so it is an upper bound of $S(x)$ and $x\in C$. This proves claim 1.

5. Claim 2. Let $z\in\Gamma$, $x=\mathrm{pr}_{1}(z)$, $y=\mathrm{pr}_{2}(z)$, so $x\in C$ by step 4, and let $u\in C$. Let $\gamma=(n,(z_{1},\dots,z_{n}))$ be any chain and put $\gamma'=(n+1,(z_{1},\dots,z_{n},z))$, again a chain. Splitting off the last summand as in step 4,

$$V_{\gamma'}(u)=V_{\gamma}(x)+y\cdot(u-x).$$

Since $V_{\gamma'}(u)\le\phi(u)$, we get $V_{\gamma}(x)\le\phi(u)-y\cdot(u-x)$ for every chain $\gamma$; the right-hand side is therefore an upper bound of $S(x)$, and as $\phi(x)$ is the least upper bound of $S(x)$,

$$\phi(x)+y\cdot(u-x)\le\phi(u).$$

As $u\in C$ was arbitrary, Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ (i) gives $y\in\partial_{C}\phi(x)$, which is claim 2.

The set $C$ and the function $\phi$ constructed in steps 2 and 3 are therefore as required: $C$ is nonempty and convex, $\phi$ is convex on $C$, and claims 1 and 2 hold.