(3.8), p. 419 — exact complementary slackness makes σ an optimal assignment and (g^{C̄}, g) an optimal dual pair
ProvedCompOT.Auction.eq_3_8assignment-problemcomplementary-slacknessdualityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a cost matrix, a dual vector and a permutation of such that, for every ,
Then both are optimal:
- is an optimal assignment: for every permutation ;
- , where , is dual feasible, for all ;
- and it is an optimal dual pair: for every dual feasible .
This is the exact form of the complementary slackness condition that the auction algorithm relaxes to ε-complementary slackness.
Formalization Note is Fin n. The optimal assignment problem (2.2) and its dual (2.20) with uniform marginals carry a factor in both objectives; it is dropped here, which does not change which assignments or dual pairs are optimal.
Preamble
import Mathlib import Definitions.Def_CompOT_Auction_Defs
Formal statement
namespace CompOT.Auction
/-- (3.8), p. 419: if a dual vector `g` and a permutation `σ` satisfy
`C_{i,σ_i} − g_{σ_i} = min_j C_{i,j} − g_j` for every `i`, then `σ` is an optimal assignment and
`(g^{C̄}, g)` is an optimal dual pair. -/
theorem eq_3_8 {n : ℕ} (C : Matrix (Fin n) (Fin n) ℝ) (g : Fin n → ℝ)
(σ : Equiv.Perm (Fin n)) (h : ∀ i, C i (σ i) - g (σ i) = ⨅ j, (C i j - g j)) :
(∀ τ : Equiv.Perm (Fin n), assignmentCost C σ ≤ assignmentCost C τ) ∧
DualFeasible C (cbarTransform C g) g ∧
∀ f' g' : Fin n → ℝ, DualFeasible C f' g' →
∑ i, f' i + ∑ j, g' j ≤ ∑ i, cbarTransform C g i + ∑ j, g j := by sorry
end CompOT.Auction
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.7, (3.8), p. 419
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.