Proof of Theorem 6, first bullet — the Mizuno–Todd–Ye predictor estimate for
ProvedSelfDualLP.Complexity.mty_predictor_bulletinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1predictor-corrector
Let and let satisfy (14) with :
where , . Put , , and . If , then for every :
This is the step-length estimate that yields the factor per predictor step.
Formalization Note is the Euclidean norm, written out as a square root of a sum of squares; the exponent of the paper is (real power). The equation of (14) is stated componentwise, with written explicitly.
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_Neighborhood open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Proof of Theorem 6, first bullet (p. 62), the Mizuno–Todd–Ye predictor estimate. Let
`n̂ ≥ 1` and let `x̂, ŝ, d̂_x, d̂_s ∈ ℝ^{n̂}` satisfy (14) with `γ = 0`: `x̂ > 0`, `ŝ > 0`,
`X̂d̂_s + Ŝd̂_x = −X̂ŝ`, `d̂_xᵀd̂_s = 0`. Write `μ̂ = x̂ᵀŝ/n̂`, `x̂(α) = x̂ + αd̂_x`,
`ŝ(α) = ŝ + αd̂_s`, `μ̂(α) = x̂(α)ᵀŝ(α)/n̂`. If `‖X̂ŝ − μ̂e‖ ≤ (1/4)μ̂` then for every
`α ∈ [0, 8^{−1/4}/√n̂]`: `x̂(α) > 0`, `ŝ(α) > 0`, `‖X̂(α)ŝ(α) − μ̂(α)e‖ ≤ (1/2)μ̂(α)` and
`μ̂(α) = (1 − α)μ̂`. -/
theorem mty_predictor_bullet {N : ℕ} (hN : 1 ≤ N) (x s dx ds : Fin N → ℝ)
(hx : ∀ j, 0 < x j) (hs : ∀ j, 0 < s j)
(hnewton : ∀ j, x j * ds j + s j * dx j = -(x j * s j - 0 * muHat x s))
(horth : dx ⬝ᵥ ds = 0)
(hcent : deviationHat x s ≤ (1 / 4) * muHat x s) :
∀ α : ℝ, 0 ≤ α → α ≤ (8 : ℝ) ^ (-(1 / 4 : ℝ)) / Real.sqrt N →
(∀ j, 0 < (x + α • dx) j) ∧ (∀ j, 0 < (s + α • ds) j) ∧
deviationHat (x + α • dx) (s + α • ds) ≤ (1 / 2) * muHat (x + α • dx) (s + α • ds) ∧
muHat (x + α • dx) (s + α • ds) = (1 - α) * muHat x s := by sorry
end SelfDualLP.Complexity
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 62, proof of Theorem 6, first bullet (with (14) on p. 61)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.