Theorem 8 — τᵏ ≥ (1 − 2β)/(eᵀx̄ + eᵀs̄ + 1) if (LP) has an optimum; otherwise κᵏ ≥ (1 − 2β)ε/(n + 1) and τᵏ/θᵏ is bounded
ProvedSelfDualLP.Output.theorem_8Let , , be real data, and let be the iterates of the Mizuno–Todd–Ye predictor–corrector algorithm applied to the homogeneous self-dual program (HLP) under the choice (7), with .
- If (LP) possesses an optimal solution, then
where and are any optimal solution pair for (LP) and (LD). 2. Otherwise there is a fixed number , independent of , such that for all
and
So either stays bounded away from zero, which happens exactly when (LP) has an optimal solution, or and tend to zero at the same rate while stays bounded away from zero. This lets one decide the status of (LP) from an approximate iterate, without running the algorithm to an exact solution.
Formalization Note is the algorithm's fixed parameter , so and . "Otherwise" is the negation of "(LP) possesses an optimal solution": it covers infeasible (LP), and feasible but unbounded (LP). The number is chosen after the data and the sequence and before ; it may depend on the instance. The chain is kept as printed, with divisions; all denominators are positive along the sequence (, on ), so no link holds because of Lean's convention . The statement quantifies over predictor–corrector sequences; on an instance where the maximum in (13) is not attained, no such sequence exists and the statement is vacuous there.
import Mathlib import Definitions.Def_SelfDualLP_Complexity_LPData import Definitions.Def_SelfDualLP_Output_HLP import Definitions.Def_SelfDualLP_Output_Neighborhood import Definitions.Def_SelfDualLP_Output_PCSequence open Matrix
namespace SelfDualLP.Output
/-- Theorem 8 (p. 63), with `β = 1/4`. Let `(yᵏ, xᵏ, τᵏ, θᵏ, sᵏ, κᵏ)` be the iterates of the
predictor–corrector algorithm on (HLP) under (7).
* If (LP) possesses an optimal solution, then `τᵏ ≥ (1 − 2β)/(eᵀx̄ + eᵀs̄ + 1)` for all `k`,
where `x̄` and `(ȳ, s̄)` are any optimal solution pair for (LP) and (LD);
* otherwise there is a fixed `ε > 0`, independent of `k`, such that for all `k`
`κᵏ ≥ (1 − 2β)ε/(n + 1)` and
`(1 − 2β)/(2(n + 1)) ≤ (1 − 2β)/κᵏ ≤ τᵏ/θᵏ ≤ (1 + 2β)/κᵏ ≤ (n + 1)(1 + 2β)/((1 − 2β)ε)`. -/
theorem theorem_8 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(z : ℕ → HLPPoint m n) (hz : IsPCSequence A b c z) :
(SelfDualLP.Complexity.LPHasSolution A b c →
∀ (xbar : Fin n → ℝ) (ybar : Fin m → ℝ) (sbar : Fin n → ℝ),
SelfDualLP.Complexity.LPOptimal A b c xbar → SelfDualLP.Complexity.LDOptimal A b c ybar sbar →
∀ k, (1 - 2 * beta) / (ones n ⬝ᵥ xbar + ones n ⬝ᵥ sbar + 1) ≤ (z k).τ) ∧
(¬ SelfDualLP.Complexity.LPHasSolution A b c →
∃ ε : ℝ, 0 < ε ∧ ∀ k,
(1 - 2 * beta) * ε / ((n : ℝ) + 1) ≤ (z k).κ ∧
(1 - 2 * beta) / (2 * ((n : ℝ) + 1)) ≤ (1 - 2 * beta) / (z k).κ ∧
(1 - 2 * beta) / (z k).κ ≤ (z k).τ / (z k).θ ∧
(z k).τ / (z k).θ ≤ (1 + 2 * beta) / (z k).κ ∧
(1 + 2 * beta) / (z k).κ ≤ ((n : ℝ) + 1) * (1 + 2 * beta) / ((1 - 2 * beta) * ε)) := by sorry
end SelfDualLP.Output
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.