Proposition 3.3, p. 405 — complementary feasible P and (f, g) are primal and dual optimal
ProvedCompOT.Duality.proposition_3_3complementary-slacknesskantorovich-dualityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , be histograms and . Suppose is primal feasible, is dual feasible, and and are complementary w.r.t. (Definition 3.1: whenever ). Then
- is optimal for the primal problem: for all ;
- is optimal for the dual problem: for all .
This is the sufficiency half of complementary slackness: complementarity certifies optimality of both solutions at once.
Formalization Note The page cites the primal and dual as "(2.24)" and "(2.11)"; these are the measure-theoretic problem and the discrete primal. The intended problems are the discrete primal (2.11) and dual (2.20), which is what is stated here.
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- Proposition 3.3, p. 405: if `P ∈ U(a, b)` and `(f, g) ∈ R(C)` are complementary
(Definition 3.1), then `P` is optimal for the primal (2.11) and `(f, g)` is optimal for the
dual (2.20). -/
theorem proposition_3_3 {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)
(hcomp : Complementary C P f g) :
CompOT.Assignment.IsOptimalCoupling C a b P ∧ IsDualOptimal C a b f g := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 3.3 and Definition 3.1, p. 405
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.