(8) — |x − x₀| ≦ c|(Ax − b)⁺| in the max norm, with c = max_{v_S>0} a_S/v_S
ProvedHoffmanBound.ErrorBound.eq8error-boundslinear-inequalitiesmatrix-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let the system be consistent and let be the max norm. For a nonempty set of rows let be the largest absolute value of the coordinates of the rows , (6), and let
the minimum over with : the value of the zero-sum two-person game with matrix (7). Put
Then for every there is a solution of with
This makes the constant of the main theorem explicit for Case II () in terms of matrix games.
Formalization Note The maximum defining ranges over the nonempty sets of rows with ; if there is none (every row of is ), is taken to be , and then every is a solution of the consistent system, so the bound holds with .
Preamble
import Mathlib import Definitions.Def_HoffmanBound_ErrorBound_Model import Definitions.Def_HoffmanBound_ErrorBound_NormConstants
Formal statement
namespace HoffmanBound.ErrorBound
open Matrix
/-- Hoffman 1952, p. 265, (8). If `Ax ≤ b` is consistent, every `x` has a solution `x₀` with
`|x - x₀| ≤ c |(Ax - b)⁺|` (max norms), where `c = max_{v_S > 0} a_S / v_S` over the nonempty sets
`S` of rows, `a_S` as in (6) and `v_S` the game value (7). -/
theorem eq8 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hcons : (solutionSet A b).Nonempty) :
∀ x : Fin n → ℝ, ∃ x₀ ∈ solutionSet A b,
maxNorm (x - x₀) ≤ constC8 A * maxNorm (posPartVec (A *ᵥ x - b)) := by sorry
end HoffmanBound.ErrorBound
Source
Hoffman, On Approximate Solutions of Systems of Linear Inequalities, J. Res. Nat. Bur. Standards 49 (1952), pp. 264–265 (PDF pp. 2–3), §4, (6), (7), (8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.