Proposition 4.5 — entropic dual maximizers are Kantorovich feasible
ProvedCompOT.EntropicDual.proposition_4_5dualityentropyoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and be probability histograms, let , and let . Every pair maximizing the entropic dual objective satisfies for every . Consequently,
where is the unregularized Kantorovich cost. Thus the entropic dual potentials supply a feasible lower bound for ordinary optimal transport.
Formalization Note A maximizer is a pair whose objective dominates all pairs; the real infimum defining is only used with nonempty, bounded coupling sets. If a histogram has a zero entry, there is no finite maximizer, so the conditional statement has no instance there.
Preamble
import Mathlib import Definitions.Def_CompOT_EntropicDual_Defs
Formal statement
namespace CompOT.EntropicDual
/-- Proposition 4.5, pp. 452–453: every entropic dual maximizer is a feasible
Kantorovich potential and its linear objective is below the unregularized cost. -/
theorem proposition_4_5 {n m : ℕ} (C : Matrix (Fin n) (Fin m) ℝ)
(a : Fin n → ℝ) (b : Fin m → ℝ) (ε : ℝ)
(hn : 0 < n) (hm : 0 < m) (hε : 0 < ε)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(f : Fin n → ℝ) (g : Fin m → ℝ)
(hmax : ∀ f' g', dualObjEnt C a b ε f' g' ≤ dualObjEnt C a b ε f g) :
KantorovichFeasible C f g ∧
(∑ i, f i * a i) + (∑ j, g j * b j) ≤ unregCost C a b := by sorry
end CompOT.EntropicDual
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 4.5, pp. 452–453. https://doi.org/10.1561/2200000073
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.