(9) — if all A_i·A_j > 0, then |x − x₀| ≦ (a/v)|(Ax − b)⁺| in the max norm
ProvedHoffmanBound.ErrorBound.eq9error-boundslinear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let the system be consistent and suppose for all rows (including ). Let
and let be the max norm (largest absolute value of a coordinate). Then for every there is a solution of with
This is the special case of Case II () in which the constant of the main theorem is given by the entries and Gram matrix of alone.
Formalization Note The statement is in "the language of the theorem": for every some solution satisfies the bound. and are ⨅/⨆ over the rows and columns (see the definition file); for they are the attained min and max.
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, (9). If `Ax ≤ b` is consistent and all `A_i · A_j > 0`, then with
`v = min_{i,j} A_i · A_j` and `a = max_{i,j} |a_ij|`, every `x` has a solution `x₀` with
`|x - x₀| ≤ (a / v) |(Ax - b)⁺|` (max norms). -/
theorem eq9 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hcons : (solutionSet A b).Nonempty) (hpos : ∀ i j, 0 < A i ⬝ᵥ A j) :
∀ x : Fin n → ℝ, ∃ x₀ ∈ solutionSet A b,
maxNorm (x - x₀) ≤ aMax A / vMin 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), p. 265 (PDF p. 3), §4, (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.