§3.2, p. 403 — (f, f^C) ∈ R(C), and f^C is the largest g with (f, g) ∈ R(C)
ProvedCompOT.Duality.sec_3_2_ctransform_admissiblec-transformkantorovich-dualityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , and , and let be its -transform, . Then
- , i.e. for all ;
- is the largest such vector: if satisfies , then elementwise.
In words: once is frozen, is the best admissible choice of the second dual variable. This is the fact behind the semi-dual formulation (3.5).
Formalization Note The hypothesis makes the minimum over well defined; the book's index sets are nonempty throughout.
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- §3.2, p. 403: `(f, f^C) ∈ R(C)`, and `f^C` is the largest vector `g` with `(f, g) ∈ R(C)`.
The index set `⟦n⟧` is nonempty (`n ≥ 1`), so that `f^C` is a genuine minimum. -/
theorem sec_3_2_ctransform_admissible {n m : ℕ} (hn : 0 < n) (C : Matrix (Fin n) (Fin m) ℝ)
(f : Fin n → ℝ) :
dualFeasible C f (cTransform C f) ∧
∀ g : Fin m → ℝ, dualFeasible C f g → g ≤ cTransform C f := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.2, p. 403, sentence following the definition of f^C
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.