Lemma 3 — on the set E there is d_S > 0 with Fₘ((Mx)⁺) ≧ d_S Fₙ(x)
ProvedHoffmanBound.ErrorBound.lemma3compactnesslinear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be positive homogeneous functions in the sense of (3). Let be a set of rows of , let be the matrix obtained from by substituting for the rows not in , let , and let be the set of all such that (i) and (ii) the origin is the point of nearest to . Then there exists such that
The constant is chosen before ; together with Lemma 2 it gives the main theorem with .
Formalization Note is an arbitrary Finset of row indices (including and all rows), and keeps all rows, with zeros in the rows outside .
Preamble
import Mathlib import Definitions.Def_HoffmanBound_ErrorBound_Model
Formal statement
namespace HoffmanBound.ErrorBound
open Matrix
/-- Hoffman 1952, p. 263, Lemma 3. Let `M` be obtained from `A` by substituting `0` for the rows
not in `S`, `Ω = {z | M z ≤ 0}`, and `E` the set of `x ∉ Ω` whose nearest point in `Ω` is the
origin. For `F_n`, `F_m` satisfying (3) there is `d_S > 0` with `F_m((M x)⁺) ≥ d_S F_n(x)` for all
`x ∈ E`. -/
theorem lemma3 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (S : Finset (Fin m))
(Fn : (Fin n → ℝ) → ℝ) (Fm : (Fin m → ℝ) → ℝ)
(hFn : IsPosHomogeneous Fn) (hFm : IsPosHomogeneous Fm) :
∃ dS : ℝ, 0 < dS ∧ ∀ x ∈ setE A S, dS * Fn x ≤ Fm (posPartVec (rowsOn A S *ᵥ x)) := by sorry
end HoffmanBound.ErrorBound
Source
Hoffman, On Approximate Solutions of Systems of Linear Inequalities, J. Res. Nat. Bur. Standards 49 (1952), p. 263 (PDF p. 1), Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.