Proof of Lemma 12, p. 14 — weak duality on the relaxed constraints: bᵀŷ ≤ (c + κe)ᵀx* ≤ cᵀx* + rκ
ProvedQZeroSum19.LPReduce.weak_duality_relaxedlinear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-duality
Let , , , and . Let satisfy and the relaxed constraints , and let be feasible for the dual (5), , , with . Then
In the proof of Lemma 12 this is applied with and an optimal dual solution with , giving .
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem weak_duality_relaxed {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (r κ : ℝ) (yhat : Fin m → ℝ) (x : Fin n → ℝ) (hyhat : ∀ j, 0 ≤ yhat j)
(hκ : 0 ≤ κ) (hAy : ∀ i, (A *ᵥ yhat) i ≤ c i + κ) (hx : IsDualFeasible A b x)
(hxr : ∑ i, x i ≤ r) :
b ⬝ᵥ yhat ≤ (fun i => c i + κ) ⬝ᵥ x ∧ (fun i => c i + κ) ⬝ᵥ x ≤ c ⬝ᵥ x + r * κ := by sorry
end QZeroSum19.LPReduce
Source
van Apeldoorn and Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180v1, p. 14, proof of Lemma 12, display bᵀŷ ≤ (c + e6Rε‴)ᵀx* ≤ OPT + 6Rrε‴
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.