Lemma 3 — the corrector returns to N₂(1/4)
ProvedAdaptiveStepIPM.PredCorr.lemma_3interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
An iteration of Algorithm 1 that starts in returns to :
This one-iteration invariant yields the paper's assertion that every iterate of a run lies in the inner neighborhood.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Algorithm
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Lemma 3, printed p. 7, in its equivalent one-iteration invariant form. -/
theorem lemma_3 {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x s xNext sNext : Fin n → ℝ)
(hxs : N2 A b c (1 / 4) x s)
(hstep : Alg1Step A b c x s xNext sNext) :
N2 A b c (1 / 4) xNext sNext := 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. 7, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.