Cyclically monotone sets admit c-concave contact potentials

For a finite real cost c, a pair of potentials φ and ψ satisfying the Kantorovich dual constraint φ x + ψ y ≤ c (x, y) meets it with equality on its contact set, and no finite rearrangement of the targets of finitely many contact points can lower the total cost: a contact set is c-cyclically monotone. This file proves the converse, which is the theorem of Rockafellar and Rüschendorf: every c-cyclically monotone set is contained in the c-superdifferential of a c-concave potential. Together the two directions characterise cyclical monotonicity by the existence of a potential.

The potential is the explicit one of Rüschendorf's proof. Fix a base point p of the set S and read a finite chain p = w 0, w 1, …, w n of points of S followed by a target x as the telescoping quantity

c (x, (w n).2) + ∑ i, c ((w (i + 1)).1, (w i).2) - ∑ i, c (w i);

the potential at x is the infimum of that quantity over all such chains. Closing a chain back at the base point turns exactly that quantity into the cyclical-monotonicity inequality for the cycle, so the infimum is 0 at the base point rather than -∞; and appending one further point of S to a chain shows that the potential decreases by at most the corresponding cost difference, which is what puts every point of S in the superdifferential. Away from S the infimum can be -∞, so the potential is EReal-valued, as the c-transform interface requires. Replacing it by its double c-transform makes it c-concave without shrinking the superdifferential.

This is the algebraic half of the theory: no measure, topology, semicontinuity, or integrability hypothesis appears, and the cost is an arbitrary real-valued function on a product of bare types.

Main statements

• TauCeti.isCyclicallyMonotone_contactSet — the contact set of a dual feasible pair is c-cyclically monotone, with TauCeti.isCyclicallyMonotone_cSuperdifferential its specialisation to a potential and its own c-transform;
• TauCeti.IsCyclicallyMonotone.exists_isCConcave_subset_cSuperdifferential — the theorem of Rockafellar and Rüschendorf: a c-cyclically monotone set lies in the c-superdifferential of a c-concave potential;
• TauCeti.isCyclicallyMonotone_iff_exists_isCConcave — the resulting characterisation.

Implementation notes

The chain value and the potential built from it are the proof's own scaffolding and are kept private: the representation theorem exposes the potential only through the existential, and a consumer that needs a named potential obtains one from it. The empty set is cyclically monotone and has no base point, so it is given the c-transform of the zero potential.

The extended-nonnegative counterpart of the first statement, for the dual pair of real potentials used by the primal interface, is TauCeti.DualFeasible.isCyclicallyMonotone_dualContactSet. The two live on different costs and different potential types — ℝ≥0∞ and ℝ there, ℝ and EReal here — and neither follows from the other: the representation theorem below needs cancellative differences of costs, which is why it is stated on the real side.

References

• R. T. Rockafellar, Characterization of the subdifferentials of convex functions, Pacific J. Math. 17 (1966), 497--510.
• L. Rüschendorf, On c-optimal random variables, Statist. Probab. Lett. 27 (1996), 267--270.
• C. Villani, Topics in Optimal Transportation, Graduate Studies in Mathematics 58, 2003, §2.3.

Contact sets are cyclically monotone

theorem TauCeti.isCyclicallyMonotone_contactSet {X : Type u} {Y : Type v} {c : X × Y → ℝ} {φ : X → EReal} {ψ : Y → EReal} (hfeas : ∀ (x : X) (y : Y), φ x + ψ y ≤ ↑(c (x, y))) : IsCyclicallyMonotone c (contactSet c φ ψ)

The contact set of a dual feasible pair of potentials is c-cyclically monotone: at a contact point both potentials are finite and their sum is the cost, so rearranging the targets of finitely many contact points can only increase the total cost.

theorem TauCeti.isCyclicallyMonotone_cSuperdifferential {X : Type u} {Y : Type v} (c : X × Y → ℝ) (φ : X → EReal) : IsCyclicallyMonotone c (cSuperdifferential c φ)

The c-superdifferential of a potential is c-cyclically monotone.

The Rockafellar potential

The representation theorem

theorem TauCeti.IsCyclicallyMonotone.exists_isCConcave_subset_cSuperdifferential {X : Type u} {Y : Type v} {c : X × Y → ℝ} {S : Set (X × Y)} (hS : IsCyclicallyMonotone c S) : ∃ (φ : X → EReal), IsCConcave c φ ∧ S ⊆ cSuperdifferential c φ

The theorem of Rockafellar and Rüschendorf. Every c-cyclically monotone set is contained in the c-superdifferential of a c-concave potential: there is a φ with φ x + φᶜ y = c (x, y) at every point (x, y) of the set, where φᶜ is the infimal c-transform of φ.

theorem TauCeti.isCyclicallyMonotone_iff_exists_isCConcave {X : Type u} {Y : Type v} (c : X × Y → ℝ) (S : Set (X × Y)) : IsCyclicallyMonotone c S ↔ ∃ (φ : X → EReal), IsCConcave c φ ∧ S ⊆ cSuperdifferential c φ

Cyclical monotonicity is exactly a contact-set condition. A set of pairs is c-cyclically monotone if and only if it lies in the c-superdifferential of some c-concave potential.