Lemma 2(c) — in , ; in ,
ProvedAdaptiveStepIPM.WideNbhd.lemma_2cinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and with . For a pair let and , that is .
- If , then (Euclidean norm).
- If , then for each
so .
Combined with Lemma 1(c), part 1 bounds the second-order term by in the wide neighbourhood, which is what gives the bound of Theorem 2.
Formalization Note The four inequalities of the chain are stated separately for each coordinate , together with the conclusion on . The standing condition (so that is defined) is a hypothesis.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Lemma 2(c) of Mizuno–Todd–Ye (p. 6): let `β, γ ∈ (0, 1)` with `γ ≤ 2(1 − β)`, `μ = xᵀs/n` and
`r = (XS)^{-0.5}(γμe − Xs)`. If `(x, s) ∈ N_∞⁻(β)` then `‖r‖² ≤ nμ`. Moreover, if
`(x, s) ∈ N_∞(β)` then for each `j`
`√(1−β)√μ ≥ (γ/√(1−β) − √(1−β))√μ ≥ r_j ≥ (γ/√(1+β) − √(1+β))√μ ≥ −√(1+β)√μ`,
so `‖r‖²_∞ ≤ (1 + β)μ`. -/
theorem lemma_2c {n m : ℕ} (hn : 1 ≤ n) (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (β γ : ℝ) (hβ0 : 0 < β) (hβ1 : β < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(hγβ : γ ≤ 2 * (1 - β)) (x s : Fin n → ℝ) :
((x, s) ∈ NinfMinus A b c β → norm2 (rvec γ x s) ^ 2 ≤ (n : ℝ) * AdaptiveStepIPM.PredCorr.mu x s) ∧
((x, s) ∈ Ninf A b c β →
(∀ j, (γ / Real.sqrt (1 - β) - Real.sqrt (1 - β)) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s) ≤
Real.sqrt (1 - β) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s) ∧
rvec γ x s j ≤ (γ / Real.sqrt (1 - β) - Real.sqrt (1 - β)) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s) ∧
(γ / Real.sqrt (1 + β) - Real.sqrt (1 + β)) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s) ≤ rvec γ x s j ∧
-(Real.sqrt (1 + β) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s)) ≤
(γ / Real.sqrt (1 + β) - Real.sqrt (1 + β)) * Real.sqrt (AdaptiveStepIPM.PredCorr.mu x s)) ∧
normInf (rvec γ x s) ^ 2 ≤ (1 + β) * AdaptiveStepIPM.PredCorr.mu x s) := 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. 6, Lemma 2(c)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.