Lemma 17.4: the assignment LP over doubly stochastic matrices has an optimal solution that is a permutation matrix
ProvedUnderstandingML.assignment_lp_integralassignment-problemdoubly-stochasticlinear-programming
Lemma 17.4. There exists an optimal solution of Equation (17.10), over doubly stochastic , that is also an optimal solution of the assignment problem (17.9), i.e. a permutation matrix.
Formally: for every cost matrix there is a permutation with for every doubly stochastic .
Preamble
import Definitions.Def_UnderstandingML_Multiclass open MeasureTheory open scoped InnerProductSpace
Formal statement
namespace UnderstandingML
/-- **Lemma 17.4** (p. 243). There exists an optimal solution of the linear program (17.10),
`min ⟨A, B⟩` over doubly stochastic `B`, that is also an optimal solution of the assignment
problem (17.9): a permutation matrix `C` with `⟨A, C⟩ ≤ ⟨A, B⟩` for every doubly stochastic `B`. -/
theorem assignment_lp_integral {r : ℕ} (A : Matrix (Fin r) (Fin r) ℝ) :
∃ σ : Equiv.Perm (Fin r), ∀ B ∈ doublyStochastic ℝ (Fin r),
matrixInner A (σ.permMatrix ℝ) ≤ matrixInner A B := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §17.4.1 p. 243, Lemma 17.4 with its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.