Lemma 5 — the step length of Algorithm 2 is at least (resp. )
ProvedAdaptiveStepIPM.WideNbhd.lemma_5interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be or , let with , let solve (2) at with parameter , and let be the scaled vectors (6). Put
- If , then for every ; hence the largest admissible step of Algorithm 2 satisfies .
- If , the same holds with in place of .
Since one iteration reduces the duality measure to , a lower bound on is a guaranteed decrease of the duality gap.
Formalization Note When the norm in a denominator is , the quotient is and the minimum is ; Lean's division by zero gives , so this case is defined as explicitly. The admissibility of every is the statement the paper's proof establishes; the bound on is stated for every greatest admissible step. The standing condition 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 5 of Mizuno–Todd–Ye (p. 10): let `β, γ ∈ (0, 1)`, `(x, s)` in the neighbourhood `N`,
`d` a solution of (2) at `(x, s)` with `γ`, `μ = xᵀs/n` and `p, q` as in (6).
If `N = N_∞(β)`, every `θ ∈ [0, θ₂]` with `θ₂ = min{1, βγμ/‖AdaptiveStepIPM.PredCorr.Pq‖_∞}` keeps `(x(θ), s(θ)) ∈ N`, so
the largest admissible `θ̄` satisfies `θ̄ ≥ θ₂`; likewise for `N = N_∞⁻(β)` with
`θ₂⁻ = min{1, βγμ/‖AdaptiveStepIPM.PredCorr.Pq‖⁻_∞}`. (The minimum is `1` when the norm is `0`.) -/
theorem lemma_5 {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)
(x s : Fin n → ℝ) (dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ)
(hd : IsDirection A x s γ dx dy ds) :
((x, s) ∈ Ninf A b c β →
(∀ θ ∈ Set.Icc (0 : ℝ) (stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds))),
(x + θ • dx, s + θ • ds) ∈ Ninf A b c β) ∧
∀ θbar, IsGreatest (admissibleSteps (Ninf A b c β) x s dx ds) θbar →
stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ≤ θbar) ∧
((x, s) ∈ NinfMinus A b c β →
(∀ θ ∈ Set.Icc (0 : ℝ) (stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds))),
(x + θ • dx, s + θ • ds) ∈ NinfMinus A b c β) ∧
∀ θbar, IsGreatest (admissibleSteps (NinfMinus A b c β) x s dx ds) θbar →
stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ≤ θbar) := 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. 10, Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.