Kantorovich duality and the c-transform

For a clean strong-duality setting, take compact metric source and target spaces, probability marginals, and a finite continuous cost c. Potentials f and g are feasible if f(x) + g(y) is at most c(x, y) everywhere. Integrating this inequality against any coupling replaces the integral of f(x) by its μ-integral and the integral of g(y) by its ν-integral. Thus every feasible dual objective is at most every feasible primal objective.

Kantorovich duality states that the largest dual value equals the smallest primal value in this setting, and suitable continuous maximizing potentials exist. The weak-duality inequality is elementary; equality of the optima is the substantial theorem. Noncompact spaces and less regular costs admit broader formulations, but their integrability and attainment assumptions must be checked separately. One should not transplant every compact-space conclusion merely because the formal inequality still makes sense.

For a fixed f, feasibility requires g(y) to be at most c(x, y) − f(x) for every source x. Taking the infimum over x therefore gives the largest admissible g. This is the c-transform fᶜ. Replacing any smaller g by fᶜ cannot reduce the dual objective because ν is a positive measure. With our convention the transform uses an infimum, not the supremum used in the ordinary convex conjugate.

Applying the analogous transform again produces fᶜᶜ, which is at least f and is called a c-concave representative when equality holds. This process improves feasible potentials while preserving the direction of the inequality. In a finite problem, each transformed value is a minimum over a row or column of the cost matrix. Costs, potentials, and transforms must use the same units and any factor of one-half in the quadratic cost must be maintained throughout.

For a feasible plan and feasible dual potentials, the primal–dual gap is the integral of the nonnegative slack c − f − g. If their objective values agree, the slack is zero almost everywhere under the plan. This complementary-slackness condition identifies allowed optimal pairs. A zero-slack pair need not carry positive mass, because marginal constraints still decide how mass can be distributed among all such pairs.

The dual therefore provides both a numerical certificate and a geometric contact set. In the quadratic setting the contact relation will connect transport maps to convex potentials, but duality alone does not guarantee differentiability or graph structure. Numerical approximate potentials require an actual feasibility check before their objective is a valid lower bound. Agreement of two unconstrained solver printouts is not the same as a verified primal–dual certificate.