Remark 2.21, p. 385 — weak duality: ⟨C, P⟩ ≥ Σ P_{ij}(f_i + g_j) = ⟨f, a⟩ + ⟨g, b⟩
ProvedCompOT.Duality.remark_2_21_weak_dualitykantorovich-dualityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1weak-duality
Let and be histograms (nonnegative vectors summing to ), let , let be a transport plan and let , i.e. for all . Then
This is the easy half of Kantorovich duality: every admissible pair of prices gives a lower bound on the cost of every transport plan, hence on .
Formalization Note The three relations of the display are stated as a conjunction, with the sums written explicitly. The histogram hypotheses , are the book's standing convention for (notation section, and (2.11)).
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- Remark 2.21, display on p. 385: for a transport plan `P ∈ U(a, b)` and prices
`(f, g) ∈ R(C)`, `∑ P_{ij} C_{ij} ≥ ∑ P_{ij} (f_i + g_j) = (∑_i f_i ∑_j P_{ij}) + (∑_j g_j ∑_i P_{ij})
= ⟨f, a⟩ + ⟨g, b⟩`. -/
theorem remark_2_21_weak_duality {n m : ℕ} (a : Fin n → ℝ) (b : Fin m → ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(C P : Matrix (Fin n) (Fin m) ℝ) (hP : P ∈ CompOT.Assignment.couplings a b)
(f : Fin n → ℝ) (g : Fin m → ℝ) (hfg : dualFeasible C f g) :
∑ i, ∑ j, P i j * (f i + g j) ≤ ∑ i, ∑ j, P i j * C i j ∧
∑ i, ∑ j, P i j * (f i + g j) = (∑ i, f i * ∑ j, P i j) + (∑ j, g j * ∑ i, P i j) ∧
(∑ i, f i * ∑ j, P i j) + (∑ j, g j * ∑ i, P i j) = dualObj a b f g := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Remark 2.21, display on p. 385 (preceding text on p. 384)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.