(You may see the rest of the lecture notes here).
See my handwritten notes.
The following is a rough transcription of my handwritten notes, processed with an LLM.
Today:
- Rockafellar’s theorem
- The dual problem
From last time:
Theorem: If $\Gamma \subset X\times Y$ is $c$-cyclically monotone, there exists a $c$-convex function $\phi: X \to \mathbb{R}$ s.t.
\[(x,y) \in \Gamma \Rightarrow y \in \partial_c\phi(x).\]Proof (continued).
Last time we fixed $(x_\ast, y_\ast)$ and introduced the function $\phi: X \to \mathbb{R}$ by
\[\begin{aligned} \phi(x) = \sup\Big\{ & -c(x,y_0) + c(x_0,y_0) \\ & + \sum_{k=1}^n -c(x_{k-1},y_k) + c(x_k,y_k) \\ & \;\Big|\; \{(x_k,y_k)\}_{k=0}^n \subset \Gamma, \text{ and } x_n = x_\ast,\ y_n = y_\ast \Big\} \end{aligned}\]we noted that $\phi(x_\ast) \leq 0$ by $c$-cyclical monotonicity, and that in this case $\phi$ is well defined and inherits whatever modulus of continuity $x \mapsto c(x,y)$ has that is uniform in $y$.
What remains to show is the two key facts:
(1) $\phi(x)$ is $c$-convex
(2) If $(\hat x, \hat y) \in \Gamma$, then $\hat y \in \partial_c\phi(\hat x)$
Let’s show (2) (for (1), see the exercise after the proof)
Fix $(\hat x, \hat y) \in \Gamma$. Then, $\forall\, \varepsilon > 0$ $\exists$ a sequence $\{(x_k^{(\varepsilon)}, y_k^{(\varepsilon)})\}_{k=0}^n$ s.t.
\[\begin{aligned} \phi(x) \geq & -c(x, y_0^{(\varepsilon)}) + c(x_0^{(\varepsilon)}, y_0^{(\varepsilon)}) \\ & + \Big\{ \sum_{k=1}^n -c(x_{k-1}^{(\varepsilon)}, y_k^{(\varepsilon)}) + c(x_k^{(\varepsilon)}, y_k^{(\varepsilon)}) \Big\} \quad \forall\, x \end{aligned}\]and
\[\begin{aligned} \phi(\hat x) - \varepsilon \leq & -c(\hat x, y_0^{(\varepsilon)}) + c(x_0^{(\varepsilon)}, y_0^{(\varepsilon)}) \\ & + \Big\{ \sum_{k=1}^n -c(x_{k-1}^{(\varepsilon)}, y_k^{(\varepsilon)}) + c(x_k^{(\varepsilon)}, y_k^{(\varepsilon)}) \Big\} \end{aligned}\]Since
\[\{(\hat x, \hat y), (x_0^{(\varepsilon)}, y_0^{(\varepsilon)}), \ldots, (x_n^{(\varepsilon)}, y_n^{(\varepsilon)})\} \subset \Gamma\]we have for all $x \in X$,
\[\begin{aligned} \phi(x) \geq & -c(x, \hat y) + c(\hat x, \hat y) \\ & - c(\hat x, y_0^{(\varepsilon)}) + c(x_0^{(\varepsilon)}, y_0^{(\varepsilon)}) \\ & + \sum_{k=1}^n -c(x_{k-1}^{(\varepsilon)}, y_k^{(\varepsilon)}) + c(x_k^{(\varepsilon)}, y_k^{(\varepsilon)}) \end{aligned}\]write
\[\begin{aligned} \alpha^{(\varepsilon)} := & -c(\hat x, y_0^{(\varepsilon)}) + c(x_0^{(\varepsilon)}, y_0^{(\varepsilon)}) \\ & + \sum_{k=1}^n -c(x_{k-1}^{(\varepsilon)}, y_k^{(\varepsilon)}) + c(x_k^{(\varepsilon)}, y_k^{(\varepsilon)}) \end{aligned}\]Then, $\forall\, x \in X$,
\[\phi(x) \geq -c(x, \hat y) + c(\hat x, \hat y) + \alpha^{(\varepsilon)}\]Letting $\varepsilon \to 0$ and using the definition of $\{(x_k^{(\varepsilon)}, y_k^{(\varepsilon)})\}_{k=0}^n$ we conclude that
\[\phi(x) \geq -c(x, \hat y) + c(\hat x, \hat y) + \phi(\hat x)\] \[\Rightarrow \quad \hat y \in \partial_c\phi(\hat x).\]For (1), see the following exercise $\blacksquare$
Exercise: Consider a family of $c$-convex functions $\{\phi_i\}_{i\in I}$ and define
\[\phi(x) = \sup_i \phi_i(x)\]Show that if $\{\phi_i\}_i$ is equibounded and uniformly continuous then $\phi$ is $c$-convex.
The dual problem AKA the shippers’ dilemma
Let us consider the situation we presented when we introduced the discrete Kantorovich problem.
Suppose you run a shipping company, you charge an amount $\phi_i$ for the picking up of one unit of mass at a location $x_i$, and charge an amount $\psi_j$ for putting a unit of mass at location $y_j$.
Assume the amount of mass (say, lumber) at $x_i$ is $f_i$, and the demand at $y_j$ is $g_j$, with $\sum f_i = \sum g_j$. Then, the total income to the shipper is
\[\sum_{i=1}^m \phi_i f_i + \sum_{j=1}^n \psi_j g_j\]The shipper wants to make this as large as possible. However, the shipper has to contend with the constraint
\[\phi_i + \psi_j \leq c_{ij}\]for, if the opposite inequality held, the lumber mill at $x_i$ and factory $y_j$ would rather do the transportation themselves, with a lower cost of $c_{ij}$.
Therefore, we have the following maximization problem
\[\boxed{\begin{array}{ll} \text{maximize} & \displaystyle\sum_{i=1}^m \phi_i f_i + \sum_{j=1}^n \psi_j g_j \\[1em] \text{subject to} & \phi_i + \psi_j \leq c_{ij} \end{array}}\]This is the (discrete) dual problem to the Kantorovich problem.
The dual problem (general case)
Given $c: X\times Y \to \mathbb{R}$, continuous and $\mu \in \mathcal{P}(X)$, $\nu \in \mathcal{P}(Y)$ ($X, Y$ assumed compact) then, consider the following maximization problem
\[\boxed{\begin{array}{ll} \displaystyle\max_{\phi,\psi} & \displaystyle\int_X \phi\; d\mu + \int_Y \psi\; d\nu \\[1em] \text{subject to} & \phi(x) + \psi(y) \leq c(x,y) \\ & \phi \in L^1(\mu),\ \psi \in L^1(\nu) \end{array}}\](The Dual Problem)