§3.2, p. 403 — for (f, g) ∈ R(C): ⟨f, a⟩ + ⟨g, b⟩ ≤ ⟨f, a⟩ + ⟨f^C, b⟩
ProvedCompOT.Duality.sec_3_2_semidual_inequalityc-transformkantorovich-dualityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1semi-dual
Let , be histograms, , and . With the -transform of ,
Replacing by never decreases the dual objective, so the dual problem (2.20) can be reduced to a maximization over alone.
Formalization Note forces , so is a genuine minimum. Only is needed for the inequality; the full histogram hypotheses are the book's standing convention.
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- §3.2, p. 403: for histograms `a ∈ Σ_n`, `b ∈ Σ_m` and any dual feasible `(f, g) ∈ R(C)`,
`⟨f, a⟩ + ⟨g, b⟩ ≤ ⟨f, a⟩ + ⟨f^C, b⟩`. -/
theorem sec_3_2_semidual_inequality {n m : ℕ} (a : Fin n → ℝ) (b : Fin m → ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(C : Matrix (Fin n) (Fin m) ℝ) (f : Fin n → ℝ) (g : Fin m → ℝ)
(hfg : dualFeasible C f g) :
dualObj a b f g ≤ dualObj a b f (cTransform C f) := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.2, p. 403, display preceding (3.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.