(10) — if w = minᵢ(g_ii + Σ_{g_ij<0} g_ij) > 0, then |x − x₀| ≦ (a/w)||(Ax − b)⁺||
ProvedHoffmanBound.ErrorBound.eq10error-boundslinear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let the system be consistent, let be the Gram matrix of all the rows of , and suppose
Let , let be the max norm and the sum norm (sum of the absolute values of the coordinates). Then for every there is a solution of with
This is the special case of Case III (, ) singled out in Section 5.
Formalization Note The page prints the summation range in as ""; since is an matrix indexed by rows, is read as ranging over the rows. The bound is in the language of the main theorem: some solution satisfies it.
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, (10). If `Ax ≤ b` is consistent and
`w = min_i (g_ii + ∑_{j : g_ij < 0} g_ij) > 0` for the Gram matrix `g_ij = A_i · A_j` of all rows,
then with `a = max_{i,j} |a_ij|` every `x` has a solution `x₀` with
`|x - x₀| ≤ (a / w) ‖(Ax - b)⁺‖` (max norm on the left, sum norm on the right). -/
theorem eq10 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hcons : (solutionSet A b).Nonempty) (hw : 0 < wConst A) :
∀ x : Fin n → ℝ, ∃ x₀ ∈ solutionSet A b,
maxNorm (x - x₀) ≤ aMax A / wConst A * sumNorm (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), §5, (10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.