Proposition 2.4, p. 382 — Kantorovich duality: L_C(a, b) = max over (f, g) ∈ R(C) of ⟨f, a⟩ + ⟨g, b⟩
ProvedCompOT.Duality.proposition_2_4kantorovich-dualitylinear-programmingoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and be histograms and let be any cost matrix. The Kantorovich problem
admits the dual
Precisely: there exist a coupling minimizing over and a pair maximizing over , and
The maximizing are the Kantorovich potentials. This is the finite-dimensional Kantorovich duality on which the dual algorithms of the book (dual ascent, auction, Sinkhorn's dual interpretation) rest.
Formalization Note Both the minimum and the maximum are claims of the book, so both attainments are asserted, through the predicates "optimal coupling" and "dual optimal" rather than through real infima/suprema. The histogram hypotheses are essential: if then is empty and the dual is unbounded.
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- Proposition 2.4, p. 382 (Kantorovich duality (2.20)): for histograms `a ∈ Σ_n`, `b ∈ Σ_m` and
any cost matrix `C`, the minimum `L_C(a, b)` of (2.11) is attained by some `P ∈ U(a, b)`, the maximum
of `⟨f, a⟩ + ⟨g, b⟩` over `R(C)` is attained by some `(f, g)`, and the two values are equal. -/
theorem proposition_2_4 {n m : ℕ} (a : Fin n → ℝ) (b : Fin m → ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(C : Matrix (Fin n) (Fin m) ℝ) :
∃ (P : Matrix (Fin n) (Fin m) ℝ) (f : Fin n → ℝ) (g : Fin m → ℝ),
CompOT.Assignment.IsOptimalCoupling C a b P ∧ IsDualOptimal C a b f g ∧ CompOT.Assignment.frob C P = dualObj a b f g := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 2.4, (2.20)–(2.21), p. 382
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.