Lemma 2(b) — corrector residual bound
ProvedAdaptiveStepIPM.PredCorr.lemma_2binterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . For the scaled residual of (6) at ,
This bounds the full corrector direction starting from the outer neighborhood.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Direction open Matrix
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Lemma 2(b), printed p. 5. -/
theorem lemma_2b {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x s : Fin n → ℝ) (β : ℝ) (hβ0 : 0 < β) (hβ1 : β < 1)
(hxs : N2 A b c β x s) :
(l2Norm (scaledR x s 1)) ^ 2 ≤ β ^ 2 * mu x s / (1 - β) := by sorry
end AdaptiveStepIPM.PredCorr
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 2(b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.