Lemma 1(a) — Euclidean bound on the second-order term
ProvedAdaptiveStepIPM.PredCorr.lemma_1ainterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let , and let solve system (2). With the scaled vectors of (6) and ,
This inequality bounds the nonlinear term in the centrality equation and is used for both predictor and corrector steps.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Direction open Matrix
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Lemma 1(a), equation (9), printed p. 5. -/
theorem lemma_1a {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 → ℝ) (γ : ℝ)
(hγ0 : 0 ≤ γ) (hγ1 : γ ≤ 1)
(hxs : F0 A b c x s)
(hd : SearchDirection A x s γ dx dy ds) :
l2Norm (Pq x s dx ds) ≤
(Real.sqrt 2 / 4) * (l2Norm (scaledR x s γ)) ^ 2 := 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 1(a), equation (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.