Lemma 1(c) — and
ProvedAdaptiveStepIPM.WideNbhd.lemma_1cinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be positive, , a solution of (2) at with parameter , and the scaled vectors (6), . Write for the Euclidean norm, for the maximum norm, and for the maximum norm of the negative (positive) part of . Then
These bounds on the second-order term turn the neighbourhood conditions into lower bounds on the step length (Lemma 5 and the proof of Theorem 2).
Formalization Note The inequality appears twice in the paper's display and once in the Lean conjunction. Only is assumed of the pair.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Lemma 1(c) of Mizuno–Todd–Ye (p. 5): for a solution `d` of (2) at `x, s > 0` with
`γ ∈ [0, 1]`, and `p, q, r` as in (6),
`‖AdaptiveStepIPM.PredCorr.Pq‖⁻_∞ ≤ ‖r‖²/4 ≤ n‖r‖²_∞/4`, `‖AdaptiveStepIPM.PredCorr.Pq‖⁺_∞ ≤ ‖r‖²_∞/4` and `‖AdaptiveStepIPM.PredCorr.Pq‖_∞ ≤ ‖r‖²/4 ≤ n‖r‖²_∞/4`
(`‖r‖` the `ℓ₂` norm, `‖r‖_∞` the `ℓ_∞` norm). -/
theorem lemma_1c {n m : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (x s : Fin n → ℝ)
(hx : ∀ j, 0 < x j) (hs : ∀ j, 0 < s j) (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ ≤ 1)
(dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ) (hd : IsDirection A x s γ dx dy ds) :
normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ≤ norm2 (rvec γ x s) ^ 2 / 4 ∧
norm2 (rvec γ x s) ^ 2 / 4 ≤ (n : ℝ) * normInf (rvec γ x s) ^ 2 / 4 ∧
normInfPos (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ≤ normInf (rvec γ x s) ^ 2 / 4 ∧
normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ≤ norm2 (rvec γ x s) ^ 2 / 4 := by sorry
end AdaptiveStepIPM.WideNbhd
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 5, Lemma 1(c)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.