Proof of Lemma 12, p. 14 — case λ* > 0: OPT < α
ProvedQZeroSum19.LPReduce.lemma_12_poslinear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let the LP pair (4)/(5) with data , , satisfy the standing assumptions of §4 with constants , and optimal value , let , and let be the value of the game (6) (second row ). Then
This is the first case of the proof of Lemma 12: a positive game value certifies that the LP cannot reach the objective level .
Formalization Note is the infimum over the column player's simplex of the largest entry of . No bound on is needed in this case.
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem lemma_12_pos {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(R r OPT α : ℝ) (hLP : LPStanding A b c R r OPT) :
0 < QZeroSum19.GK.gameValue (gameMatrix A b c α R) → OPT < α := 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, first case ("which is a contradiction, hence OPT < α")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.