Lemma 1(b) — for each
ProvedAdaptiveStepIPM.WideNbhd.lemma_1binterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be positive, , , and let solve the Newton system (2)
With the scaled vectors (6), , , , and the Euclidean norm, for each
The product is the -th component of the second-order term of Newton's method; this componentwise bound is the source of every step-length estimate in the paper.
Formalization Note The paper states the lemma for in a neighbourhood ; only is assumed here. is the square of the explicitly defined norm.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Lemma 1(b) of Mizuno–Todd–Ye (p. 5): for a solution `d` of (2) at `x, s > 0` with
`γ ∈ [0, 1]`, and `p, q, r` as in (6), `−‖r‖²/4 ≤ p_j q_j ≤ r_j²/4` for each `j`
(`‖·‖` the `ℓ₂` norm). -/
theorem lemma_1b {n m : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (x s : Fin n → ℝ)
(hx : ∀ j, 0 < x j) (hs : ∀ j, 0 < s j) (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ ≤ 1)
(dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ) (hd : IsDirection A x s γ dx dy ds)
(j : Fin n) :
-(norm2 (rvec γ x s) ^ 2 / 4) ≤ pvec x s dx j * qvec x s ds j ∧
pvec x s dx j * qvec x s ds j ≤ rvec γ x s j ^ 2 / 4 := by sorry
end AdaptiveStepIPM.WideNbhd
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(b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.