§3.2, proof, p. 14 — convex combinations of LP solutions are LP solutions
ProvedSymBoolPCSP.LPRounding.convex_combinationconvexitylinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a family of Boolean promise relations and an instance with variables. Let be solutions of the LP relaxation of §3.2 and let be rationals with . Then
is also a solution of the LP relaxation.
In the proof of correctness this is applied to the columns of the matrix of LP solutions found by the algorithm, so that is a solution for every probability vector .
Formalization Note The paper states the fact for the columns of ; this item states the general convexity of the solution set over , for any finite number of solutions.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_LPRounding_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.LPRounding
/-- §3.2, proof, p. 14: any convex combination of LP solutions is an LP solution. (The
paper applies this to the `n` columns of the matrix `M`; this is the general convexity.) -/
theorem convex_combination {τ : Type} {ar : τ → ℕ} (𝔸 : RelStruct τ ar Bool)
(X : Instance τ ar) {m : ℕ} (u : Fin m → Fin X.n → ℚ) (hu : ∀ k, IsHullLPSol 𝔸 X (u k))
(lam : Fin m → ℚ) (hlam0 : ∀ k, 0 ≤ lam k) (hlam1 : ∑ k, lam k = 1) :
IsHullLPSol 𝔸 X (∑ k, lam k • u k) := by sorry
end SymBoolPCSP.LPRounding
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 14, §3.2, proof (second paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.