Generated Jacobian Equations, part 2/n


(21 Feb 2019)

Today I am going to explain how generating functions define a duality structure, discuss the first few examples, and introduce the subdifferential.

A Generating Function gives a duality structure between $\Omega$ and $\overline{\Omega}$

In the previous post I gave a definition of a Generating Function $G(x,y,z)$. However, in less precise terms, a Generating Function is best thought of as a “duality structure” between real valued functions in $\Omega$ and real valued functions in $\overline{\Omega}$. By this I mean an operation that transforms a real valued function in $\Omega$ into a real valued function in $\overline{\Omega}$, and viceversa.

The transform of a function $v:\overline{\Omega}\to\mathbb{R}$ is a new function, $v^*:\Omega\to\mathbb{R}$ defined by

\[v^*(x) = \sup \limits_{y\in \overline{\Omega}} G(x,y,v(y)),\]

while the transform of a function $u:\Omega\to\mathbb{R}$ yields a function $u^*:\overline{\Omega}\to \mathbb{R}$ given by the formula

\[u^*(y) = \sup \limits_{x \in \Omega} H(x,y,u(x)).\]

A pair of functions $u,v:\Omega,\overline{\Omega}\to\mathbb{R}$ will be called a conjugate pair if $u= v^* $ and $v=u^*$, note that in this case

\[G(x,y,v(y)) \leq u(x) \text{ and } H(x,y,u(x)) \leq v(y) \text{ for all } x\in\Omega,\;y\in\overline{\Omega},\]

where for fixed $x$, there is at least one $y$ for which the first inequality becomes an equality, and for fixed $y$, there is at least one $x$ for which the second inequality becomes an equality.

Now, let us discuss some concrete (and not so concrete) examples.

Example 1 (Standard Legendre duality): The most popular instance of this is the Legendre transform between functions in Euclidean space,

\[v^*(x) := \sup \limits_{y\in \mathbb{R}^d} \{x\cdot y-v(y)\},\]

which corresponds in the definition above to the special case where $G(x,y,z) = x\cdot y -z$ (note that in this case $H(x,y,u) = G(x,y,u)$).

Example 2 (Polar Dual): A convex body is a bounded convex set $K\subset \mathbb{R}^d$ with non-empty interior. The polar dual of a convex body is the convex set

\[K^* := \{ \xi \in \mathbb{R}^d \mid \eta \cdot \xi \leq 1 \;\text{ for all } \eta \in K \}.\]

It is well known that $(K^* )^* = K$, so this defines a duality between convex bodies. This duality can be captured in terms of a generating function when expressed in the right variables.

First, we must describe convex bodies in terms of a function. Suppose that the origin of the system of coordinates lies in the interior of $K$, then $K$ is described by the radial function

\[r_K:\mathbb{S}^{d-1}\to \mathbb{R},\; r_K(x) := \sup \{ t \mid tx \in K\}.\]

In words, $r_K$ is the function on $\mathbb{S}^{d-1}$ whose radial subgraph is equal to $K$.

A straithforward calculation one leads to the following formula expressing $r_{K^*}$ in terms of $r_K$, namely

\[r_{K^*}(y) = \frac{1}{\sup \limits_{x\in \mathbb{S}^{d-1}} (x \cdot y )r_K(x)}.\]

Let $u(x)= \frac{1}{r_K(x)}$ and $v(y) = \frac{1}{r_{K^*}(y)}$. The above formula implies that $u$ and $v$ form a conjugate pair with respect to the generating function

\[G:\mathbb{S}^{d-1}\times \mathbb{S}^{d-1} \times (0,\infty) \to \mathbb{R},\;\;G(x,y,z) := \frac{x\cdot y}{z}.\]

Example 3 (The shipper’s dilemma)

The following is the shipper’s dillemma, perhaps better known as the dual problem in optimal transportation. In this problem we are given

  1. Two domains $\Omega,\overline{\Omega}$
  2. A probability measure $\mu$ in $\Omega$, and a probability measure $\nu$ in $\overline{\Omega}$.
  3. A continuous function $c:\Omega\times \overline{\Omega} \to \mathbb{R}$ known as the cost function.

Then the dual optimal transportation problem amounts to finding a pair of functions $u:\Omega\to\mathbb{R}$, $v:\overline{\Omega}\to \mathbb{R}$ maximizing


among all pairs satisfying the pointwise constraint

\[u(x)+v(y) \leq c(x,y).\]

A basic fact in optimal transportation is that this problem admits at least one solution, and the solution is given by a pair of functions $\phi,\psi$ such that

\[u(x) = \inf \limits_{y\in\overline{\Omega}}\{c(x,y)-v(x)\},\;\;v(y) = \inf \limits_{x\in\Omega}\{c(x,y)-u(x)\}.\]

In other words, the functions $-u$ and $-v$ form a conjugate pair with respect to the generating function $G(x,y,z) = -c(x,y)-z$.

Example 4 (stable matchings in economics)

Consider a situation where we have a set of types of buyers (represented by $\Omega$) and a set of types of sellets (represented by $\overline{\Omega}$). A type of buyer and a type of seller can decide to engage in a transaction resulting in a utility for each of them. Here the generating function $G(x,y,v)$ will represent this utility, as follows: if a buyer $x$ decides to engage in a transaction with seller $y$ with the seller obtaining a utility of $v$, then $x$ obtains a utility of $G(x,y,v)$.

Lastly, we are given a probability measure $\mu$ representing the distribution of buyers, and a probability measure $\nu$ representing the distribution of sellers.

We are interested in studying outcomes. This refers to three things: a function $u(x)$, a function $v(y)$, and a measure $\lambda$ over $\Omega\times \overline{\Omega}$ with marginals $\mu$ and $\nu$, respectively, such that

\[u(x) = G(x,y,v(y)) \text{ and } v(y) = H(x,y,u(x)) \text{ for } \lambda-\text{a.e.} (x,y)\]

All of this simply says that pairs $(x,y)$ given by $\lambda$ describe buyers and sellers engaging in a transaction resulting for each in a utility of $u(x)$ and $v(y)$, respectively.

An stable outcome is an outcome where each buyer $x$ is doing the best they can do given the utility profile of sellers, and conversely each seller is doing the best they can do given the utility profile of buyers. This means that in addition to the condition above, we have

\[u(x) \geq G(x,y,v(y)) \;\forall\;x\in\Omega,y\in\overline{\Omega},\\ v(y) \geq H(x,y,u(y)) \;\forall\;y\in\Omega,x\in\overline{\Omega}.\]

In other words, if $(u,v,\lambda)$ is an stable outcome, then in particular $(u,v)$ must be a conjugate pair.

Note: This problem has been studied by economists and mathematicians for many decades. For utility functions of the form $G(x,y,z) = b(x,y)-z$, the problem falls within the framework of optimal transporation, a fruitful fact that has led to many contributions by Carlier, Ekeland, McCann and many others. Such utility functions are known in the economics literature as quasi-linear utility functions, and correspond to what is known as perfectly transferable utility. Problems with imperfectly transferabe utility which are used to model e.g. high income and taxation effects require utility functions which are not quasi-linear. I am only barely acquainted with the economic literature but I hope to be able to write later about the works of Nöldeke and Samuelson; McCann and Zhang; and Galichon, Kominers, and Webers. Nöldeke and Samuelson in particular show the existence of stable matchings for non quasilinear utilities using the formalism of generating functions (which, they note corresponds to what is known as a Galois connection), while also studying a principal-agent model with non-quasilinear utility.

One last point about this example. If one has a stable outcome $(u,v,\lambda)$, then for each buyer $x_0$ there is at least one $y_0$ achieving the maximum of


The set of such sellers represent those which $x$ could buy from to realize their maximum utility. Observe that finding such a $y_0$ is the same as finding, $y_0$ such that the function $G(x,y_0,v(y_0))$ touches $u(x)$ from below at $x_0$. If there was a map $x\to y(x)$ with the property that $y(x)$ maximizes $G(x,y,v(y))$, then we say that $y(x)$ is a map implemented by $v(y)$ (note that there could be more than one map).

This lead us to our next topic.

$G$-convex functions and the subdifferential

A function $u:\Omega\to\mathbb{R}$ will be called $G$ - convex or simply convex if for every $x_0\in \Omega$ there is a $y_0 \in \overline{\Omega}$ and $z_0 \in \Omega$ such that

\[\begin{array}{rl} u(x) & \geq G(x,y_0 ,z_0) \;\forall\;x\in\Omega, \\ u(x_0 ) & = G(x_0 ,y_0 , z_0) \end{array}\]

In a similar manner we shall talk of a function $v: \overline{\Omega}\to \mathbb{R}$ being $H$ - convex or simply convex. Observe that if $u$ and $v$ form a conjugate pair, then $u$ is $G$ - convex and $v$ is $H$ - convex.

Consider a $G$-convex function, $u$ its subdifferential at $x_0 \in \Omega$ is the set

\[\partial u(x_0) = \{y \in \overline{\Omega}\;\mid\; u(x) \geq G(x,y,H(x_0,y,u(x_0))) \;\forall\;x\in\Omega \}.\]

Likewise we define the subdifferential $\partial v(y_0)$ of a $H$-convex function $v$. Often for emphasis people write $\partial_G$ or $\partial_H$ to clarify which type of subdifferential is being talked about, but in these posts I will not use such sub indices to minimize notation.

The subdifferential is always non-empty, and it could be multivalued, the best known and most used one is the standard subdifferential in convex analysis which for a convex function $u$ and point $x_0$ gives the set of all vectors $p$ representing the slopes of hyperplanes which are supporting to the graph of $u$ at $x_0$.

(Updated February 21st)

A few relevant references I forgot to add:

Caffarelli’s summer school notes on optimal transport (relevant to Example #3) Link

Nöldeke and Samuelson’s implementation duality paper (relevant to Example #4) Link

McCann and Zhang’s monopolist problem with nonlinear price prefs (relevant to Example #4) Link

For the next post in this series I plan to talk about the exponential map, discuss a few more examples from Riemannian geometry and geometric optics, and maybe start talking about the Monge-Ampère equation. I might make a post first about Nöldeke and Samuelson’s implementation duality paper and related literature.