Lemma 4 — predictor step lower bound
ProvedAdaptiveStepIPM.PredCorr.lemma_4interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
At a pair , let a predictor direction solve (2) with , and let be the greatest step whose entire prefix stays in . Define when , and otherwise. Then
and every step is admissible. The bound supplies a guaranteed decrease of the duality measure at a predictor step.
Formalization Note The zero-denominator branch is the limiting value of the printed expression, avoiding Lean's totalized division by zero.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Algorithm
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Lemma 4, printed p. 8: the lower bound and its admissibility. -/
theorem lemma_4 {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x s dx ds : Fin n → ℝ) (dy : Fin m → ℝ) (θbar : ℝ)
(hxs : N2 A b c (1 / 4) x s)
(hd : SearchDirection A x s 0 dx dy ds)
(hmax : IsGreatest {θ : ℝ | PredictorAdmissible A b c x s dx ds θ} θbar) :
PredictorAdmissible A b c x s dx ds (theta1 x s dx ds) ∧
theta1 x s dx ds ≤ θbar := 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. 8, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.