Hoffman's theorem — if Ax ≦ b is consistent, there is c > 0 with Fₙ(x − x₀) ≦ c Fₘ((Ax − b)⁺) for some solution x₀
ProvedHoffmanBound.ErrorBound.hoffman_theoremLet be a real matrix and , and suppose the system is consistent. Let on and on be positive homogeneous functions in the sense of (3): continuous, nonnegative, zero only at the origin, and for . Then there exists a constant such that for every there exists a solution of with
A point that almost satisfies the system is close to a solution, by an amount at most a fixed multiple of the violation . The constant depends on , , and but not on .
Formalization Note The page prints the display as "", dropping an opening parenthesis; the proof's last line prints , which is the reading used. and are arbitrary functions satisfying (3), not necessarily norms.
import Mathlib import Definitions.Def_HoffmanBound_ErrorBound_Model
namespace HoffmanBound.ErrorBound
open Matrix
/-- Hoffman 1952, p. 263, Theorem (Section 2). If `Ax ≤ b` is consistent and `F_n`, `F_m` satisfy
(3), there is a constant `c > 0` such that for every `x` there is a solution `x₀` with
`F_n(x - x₀) ≤ c F_m((Ax - b)⁺)`. The constant is chosen before `x`. -/
theorem hoffman_theorem {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hcons : (solutionSet A b).Nonempty)
(Fn : (Fin n → ℝ) → ℝ) (Fm : (Fin m → ℝ) → ℝ)
(hFn : IsPosHomogeneous Fn) (hFm : IsPosHomogeneous Fm) :
∃ c : ℝ, 0 < c ∧ ∀ x : Fin n → ℝ, ∃ x₀ ∈ solutionSet A b,
Fn (x - x₀) ≤ c * Fm (posPartVec (A *ᵥ x - b)) := by sorry
end HoffmanBound.ErrorBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.