Lemma 2(a) — predictor residual identity
ProvedAdaptiveStepIPM.PredCorr.lemma_2ainterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an interior feasible pair with , let and form the scaled residual of (6) with . Then
This identity converts the Lemma 1 bound into a bound in the duality measure at the predictor step.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Direction open Matrix
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Lemma 2(a), printed p. 5. -/
theorem lemma_2a {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x s : Fin n → ℝ) (hxs : F0 A b c x s) :
(l2Norm (scaledR x s 0)) ^ 2 = (n : ℝ) * mu x s := 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(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.