Proof of Theorem 3 — each iteration of Algorithm 3 decreases by at least
ProvedAdaptiveStepIPM.Potential.potential_decrease_per_iterationinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-reduction
Let , with , and . Let , let solve system (2) at with parameter , and let be a step of Algorithm 3: and for every real with . Then
Since is of order and a total decrease of order suffices, this fixed decrease per iteration is what yields the bound of Theorem 3.
Formalization Note The paper derives this from (16) and . For the latter holds because under . For it can fail, but then no step of Algorithm 3 exists (, and is unbounded below on ), so the statement holds there with no extra hypothesis; is kept as on the page.
Preamble
import Mathlib import Definitions.Def_LinearOptimization_InteriorPointPotential import Definitions.Def_AdaptiveStepIPM_Potential_Algorithm3 open Matrix
Formal statement
namespace AdaptiveStepIPM.Potential
/-- **Proof of Theorem 3, p. 12.** Under the hypotheses of (16),
one iteration of Algorithm 3 decreases the potential by at least `11n log(1/(1 − β))`:
`ψ(x(θ̄), s(θ̄)) − ψ(x, s) ≤ −11n log(1/(1 − β))`. -/
theorem potential_decrease_per_iteration {m n : ℕ} (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 → ℝ) (hN : InNinfMinus A b c β x s)
(dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ)
(hd : IsNewtonDirection A γ x s dx dy ds) (θbar : ℝ)
(hθN : InNinfMinus A b c β (lineStep x dx θbar) (lineStep s ds θbar))
(hθmin : ∀ θ : ℝ, InNinfMinus A b c β (lineStep x dx θ) (lineStep s ds θ) →
LinearOptimization.interiorPointPotential (rho n β γ)
(lineStep x dx θbar) (lineStep s ds θbar) ≤
LinearOptimization.interiorPointPotential (rho n β γ)
(lineStep x dx θ) (lineStep s ds θ)) :
LinearOptimization.interiorPointPotential (rho n β γ)
(lineStep x dx θbar) (lineStep s ds θbar) -
LinearOptimization.interiorPointPotential (rho n β γ) x s ≤
-(11 * (n : ℝ) * Real.log (1 / (1 - β))) := by sorry
end AdaptiveStepIPM.Potential
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. 12, proof of Theorem 3 (after (16))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.