Dual attainment for costs with an integrable split upper bound

Let c : X × Y → ℝ≥0∞ be a lower semicontinuous cost on a product of Polish spaces, and suppose it has an integrable split upper bound: c (x, y) ≤ ENNReal.ofReal (cX x + cY y) (the positive part of cX x + cY y) with cX ∈ L¹(μ) and cY ∈ L¹(ν). Then the Kantorovich dual problem between the probability measures μ and ν is attained by integrable potentials, and every optimal plan is concentrated on their contact set. In particular the cost is finite everywhere and the optimal cost is finite.

The potentials are feasible on a product A ×ˢ B of sets of full measure, not on all of X × Y. Nothing stronger holds in general: take X = {0, 1}, μ = δ₀, Y = ℕ with a law ν of full support and finite mean, c (0, y) = y and c (1, y) = 0. An optimal pair must have ψ y = y - φ 0 for every y, and then no real value of φ 1 satisfies φ 1 + ψ y ≤ 0 for all y. Feasibility on A ×ˢ B is still enough for weak duality, because every coupling of μ and ν gives A ×ˢ B full measure.

The proof follows Villani's. Fix an optimal plan π. By TauCeti.IsOptimalCoupling.exists_isCyclicallyMonotone_of_lowerSemicontinuous it is concentrated on a Borel c-cyclically monotone set S. Rüschendorf's potential φ₀ of S puts S inside its c-superdifferential, and TauCeti.nullMeasurable_rockafellarPotential makes it universally measurable. A Borel modification of φ₀ on a full-measure set A and the c-transform of its restriction to A give the two potentials (TauCeti.IsCoupling.exists_ae_add_eq_of_isCyclicallyMonotone). Feasibility at fixed points x₁ ∈ A and y₁ ∈ B bounds them above by c (x, y₁) - ψ y₁ and c (x₁, y) - φ x₁. Along π the two potentials add up to the cost, so each is also bounded below by minus the upper bound of the other. The split upper bound turns these two-sided estimates into integrability.

Main statements

• TauCeti.ofReal_kantorovichDualValue_le_transportCost_of_null_compl — weak duality for potentials feasible on a product of full-measure sets;
• TauCeti.IsCoupling.exists_ae_add_eq_of_isCyclicallyMonotone — a coupling concentrated on a Borel cyclically monotone set is certified by real potentials feasible on a product of full-measure sets;
• TauCeti.IsOptimalCoupling.exists_ae_mem_dualContactSet_of_le_add — every optimal plan is concentrated on the contact set of an integrable pair of potentials feasible on a product of full-measure sets;
• TauCeti.exists_kantorovichDualValue_eq_of_le_add — dual attainment: such a pair exists whose dual value is the optimal transport cost.

References

• C. Villani, Optimal Transport: Old and New, Grundlehren 338, Springer 2009, Theorem 5.10 (iii).
• L. Ambrosio and A. Pratelli, Existence and stability results in the L¹ theory of optimal transportation, in Optimal Transportation and Applications, Lecture Notes in Math. 1813, Springer 2003, Theorem 3.2.
• L. Rüschendorf, On c-optimal random variables, Statist. Probab. Lett. 27 (1996), 267--270.

theorem TauCeti.ofReal_kantorovichDualValue_le_transportCost_of_null_compl {X : Type u_1} {Y : Type u_2} [MeasurableSpace X] [MeasurableSpace Y] {μ : MeasureTheory.Measure X} {ν : MeasureTheory.Measure Y} {c : X × Y → ENNReal} {φ : X → ℝ} {ψ : Y → ℝ} {A : Set X} {B : Set Y} (hA : μ Aᶜ = 0) (hB : ν Bᶜ = 0) (hφ : MeasureTheory.Integrable φ μ) (hψ : MeasureTheory.Integrable ψ ν) (hfeas : ∀ x ∈ A, ∀ y ∈ B, ENNReal.ofReal (φ x + ψ y) ≤ c (x, y)) : ENNReal.ofReal (kantorovichDualValue μ ν φ ψ) ≤ transportCost c μ ν

Weak duality for potentials feasible on a product of full-measure sets. If integrable potentials satisfy φ x + ψ y ≤ c (x, y) for x ∈ A and y ∈ B, where Aᶜ is μ-null and Bᶜ is ν-null, then the positive part of their dual value is at most the transport cost: every coupling of μ and ν gives A ×ˢ B full measure.

theorem TauCeti.IsCoupling.exists_ae_add_eq_of_isCyclicallyMonotone {X : Type u_1} {Y : Type u_2} [MeasurableSpace X] [MeasurableSpace Y] {μ : MeasureTheory.Measure X} {ν : MeasureTheory.Measure Y} [TopologicalSpace X] [PolishSpace X] [BorelSpace X] [TopologicalSpace Y] [PolishSpace Y] [BorelSpace Y] [MeasureTheory.IsProbabilityMeasure μ] [MeasureTheory.IsProbabilityMeasure ν] {π : MeasureTheory.Measure (X × Y)} (hπ : IsCoupling π μ ν) {r : X × Y → ℝ} (hr : Measurable r) {S : Set (X × Y)} (hSmeas : MeasurableSet S) (hS : IsCyclicallyMonotone r S) (haeS : ∀ᵐ (z : X × Y) ∂π, z ∈ S) : ∃ (φ : X → ℝ) (ψ : Y → ℝ) (A : Set X) (B : Set Y), MeasurableSet A ∧ MeasurableSet B ∧ μ Aᶜ = 0 ∧ ν Bᶜ = 0 ∧ Measurable φ ∧ AEMeasurable ψ ν ∧ (∀ x ∈ A, ∀ y ∈ B, φ x + ψ y ≤ r (x, y)) ∧ ∀ᵐ (z : X × Y) ∂π, φ z.1 + ψ z.2 = r z

Real contact potentials of a cyclically monotone set. Let r be a measurable real cost on a product of Polish spaces, and let a coupling π of two probability measures be concentrated on a Borel r-cyclically monotone set S. Then there are potentials φ (Borel) and ψ (a.e.-measurable) and measurable sets A, B of full measure such that φ x + ψ y ≤ r (x, y) on A ×ˢ B and φ x + ψ y = r (x, y) for π-a.e. (x, y). The potential φ is a Borel modification of Rüschendorf's potential TauCeti.rockafellarPotential r S p, and ψ is the r-transform of its restriction to A.

theorem TauCeti.IsOptimalCoupling.exists_ae_mem_dualContactSet_of_le_add {X : Type u_1} {Y : Type u_2} [MeasurableSpace X] [MeasurableSpace Y] {μ : MeasureTheory.Measure X} {ν : MeasureTheory.Measure Y} {c : X × Y → ENNReal} [TopologicalSpace X] [PolishSpace X] [BorelSpace X] [TopologicalSpace Y] [PolishSpace Y] [BorelSpace Y] [MeasureTheory.IsProbabilityMeasure μ] [MeasureTheory.IsProbabilityMeasure ν] {π : MeasureTheory.Measure (X × Y)} (h : IsOptimalCoupling c π μ ν) (hc : LowerSemicontinuous c) {cX : X → ℝ} {cY : Y → ℝ} (hcX : MeasureTheory.Integrable cX μ) (hcY : MeasureTheory.Integrable cY ν) (hle : ∀ (x : X) (y : Y), c (x, y) ≤ ENNReal.ofReal (cX x + cY y)) : ∃ (φ : X → ℝ) (ψ : Y → ℝ) (A : Set X) (B : Set Y), MeasurableSet A ∧ MeasurableSet B ∧ μ Aᶜ = 0 ∧ ν Bᶜ = 0 ∧ MeasureTheory.Integrable φ μ ∧ MeasureTheory.Integrable ψ ν ∧ (∀ x ∈ A, ∀ y ∈ B, ENNReal.ofReal (φ x + ψ y) ≤ c (x, y)) ∧ ∀ᵐ (z : X × Y) ∂π, z ∈ dualContactSet c φ ψ

Optimal plans are certified by integrable potentials. Let c be a lower semicontinuous cost on a product of Polish spaces with an integrable split upper bound c (x, y) ≤ ENNReal.ofReal (cX x + cY y), and let π be an optimal coupling of two probability measures. Then there are integrable potentials φ, ψ and sets A, B of full measure such that the dual constraint φ x + ψ y ≤ c (x, y) holds on A ×ˢ B and π is concentrated on the contact set of (φ, ψ). Feasibility cannot be required on all of X × Y; see the module docstring.

theorem TauCeti.exists_kantorovichDualValue_eq_of_le_add {X : Type u_1} {Y : Type u_2} [MeasurableSpace X] [MeasurableSpace Y] {μ : MeasureTheory.Measure X} {ν : MeasureTheory.Measure Y} {c : X × Y → ENNReal} [TopologicalSpace X] [PolishSpace X] [BorelSpace X] [TopologicalSpace Y] [PolishSpace Y] [BorelSpace Y] [MeasureTheory.IsProbabilityMeasure μ] [MeasureTheory.IsProbabilityMeasure ν] (hc : LowerSemicontinuous c) {cX : X → ℝ} {cY : Y → ℝ} (hcX : MeasureTheory.Integrable cX μ) (hcY : MeasureTheory.Integrable cY ν) (hle : ∀ (x : X) (y : Y), c (x, y) ≤ ENNReal.ofReal (cX x + cY y)) : ∃ (φ : X → ℝ) (ψ : Y → ℝ) (A : Set X) (B : Set Y), MeasurableSet A ∧ MeasurableSet B ∧ μ Aᶜ = 0 ∧ ν Bᶜ = 0 ∧ MeasureTheory.Integrable φ μ ∧ MeasureTheory.Integrable ψ ν ∧ (∀ x ∈ A, ∀ y ∈ B, ENNReal.ofReal (φ x + ψ y) ≤ c (x, y)) ∧ kantorovichDualValue μ ν φ ψ = (transportCost c μ ν).toReal

Kantorovich dual attainment for costs with an integrable split upper bound. Let c be a lower semicontinuous cost on a product of Polish spaces with c (x, y) ≤ ENNReal.ofReal (cX x + cY y) for integrable cX and cY. Then there are integrable potentials φ, ψ, feasible on a product A ×ˢ B of sets of full measure, whose dual value is the optimal transport cost. By TauCeti.ofReal_kantorovichDualValue_le_transportCost_of_null_compl no such pair has a larger value, so the dual problem over this class is attained.