2
$\begingroup$

Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \mathbb{R}$, we may define the $c$-transforms of $\phi$ and $\psi$ as:

$$\phi^c(y)=\inf_{x\in X}c(x,y)-\phi(x)$$ $$\psi^{c}(x)=\inf_{y\in Y}c(x,y)-\psi(y)$$

If $\phi(x)=\psi^{c}(x)$ for some $\psi:Y\rightarrow \mathbb{R}$, we say that $\phi$ is $c$-concave.

$c$-concavity naturally appears in the field of optimal transport for the following reasons:

Let $OT_c(\mu,\nu)$ be the optimal transport cost with cost function $c$ between $\mu\in P(X)$ and $\nu\in P(Y)$. Then (under mild conditions on $c$, $\mu$ and $\nu$) we have the dual formulation $OT_c(\mu,\nu)=\max_{f(x)+g(y)\leq c(x,y)}\int f d\mu+\int gd\nu$. The maximizers $(f^*,g^*)$ are necessarily $c$-concave, and furthermore $(f^*)^c=g^*$. Furthermore, let $\gamma$ be a coupling of $\mu$ and $\nu$, i.e. a joint probability measure on $X\times Y$ such that $[\pi_1]_{\#}(\gamma)=\mu$ and $[\pi_2]_{\#}(\gamma)=\nu$. Then $\gamma$ is optimal (w.r.t. $OT_c$) iff $\gamma$ is supported on a $c$-cyclically monotone set, i.e. a set of the form: $\{(x,y)|\phi(x)+\phi^c(y)=c(x,y)\}$.

While these definitions are somewhat opaque at this level of generality (at least for me), there are two very natural special cases:

  1. When $X=Y=\mathbb{R}^d$ and $c(x,y)=||x-y||_2^2$, we have a nice characterization of $c$-concavity, namely that a function $\phi$ is $c$-concave iff $x\rightarrow \frac{1}{2}||x||_2^2-\phi(x)$ is convex. Furthermore, we have that $(\frac{1}{2}||x||_2^2-\phi(x))^c=(\frac{1}{2}||x||^2_2-\phi(x))^*$ where $*$ denotes convex duality. Thus the $c$-transform becomes the Legendre transform in this special case.
  2. When $X=Y$ and $c(x,y)$ is a metric on $X$, then if $\phi$ is 1-Lipschitz w.r.t. $c$, then $\phi^c=-\phi$ and in particular all $1$-Lipschitz functions are $c$-concave.

My question: Clearly convex functions and 1-Lipschitz functions interesting outside of their relationship to optimal transport. I'm wondering if there are other choices of $X,Y$ and $c$ such that the corresponding set of $c$-concave functions have been studied in their own right? It seems to me that $c$-concavity was specifically developed to generalize ideas from the very rich setting of Euclidean optimal transport with $c=\frac{1}{2}||.||^2$, so finding other examples would be very interesting to me.

$\endgroup$
1
  • $\begingroup$ Just a remark: c-convexity looks similar to conjugation in some versions of abstract convexity. $\endgroup$
    – Dirk
    Commented Jan 24 at 9:17

0