C-Convexity and Lipschitz Functions
The following definition of c-convexity is a characterization of the "buying price" and "selling price" of an external company, seen in the dual formulation of the Kantorovich problem
where is the transport cost. As long as the constraint is satisfied, the offer made by the external company is "competitive". The goal of the company is to maximize its benefit while maintaining its competitiveness, which implies the following relationships
because this way, the selling price is maximized and buying price minimized while the constraint is satisfied.
Definition (c-convexity): Let . A function is said to be -convex if and there exists some s.t. .
This is an abstract generalization of convexity, and can be motivated by the well-celebrated Fenchel Moreau theorem, which basically says for any extended real-valued function , is proper, lower semi-continuous and convex if and only if , where the asterisk denotes the convex conjugate of . When the cost function is simply the inner product on , the transform in the definition is exactly the convex conjugate of .
An important example is when is a metric function defined on some metric space . Then -convex functions coincide with the family of -Lipschitz functions (which is why the dual Kantorovich form of the Wasserstein distance is taking the supremum over all -Lipschitz functions). To see this, assume is -convex. Then by definition there exists a function s.t. . Fix , letting denote the maximizer of , we have
This shows -convex functions are -Lipschitz. Now assume is -Lipschitz, which implies
for any . If , then the RHS equals , which means the supremum of the RHS is equal to ; that is