Proof of Theorem 8 — (xᵏ − x*)ᵀ(sᵏ − s*) + (τᵏ − τ*)(κᵏ − κ*) = 0 and xᵏᵀs* + sᵏᵀx* + κᵏτ* = (n+1)μᵏ = (n+1)θᵏ
ProvedSelfDualLP.Output.orthogonality_identityinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work with (HLP) under the choice (7). Let be a feasible point, and let be a self-complementary (optimal) solution of (HLP) with . Then
and this can be rewritten as
In the proof of Theorem 8 it is applied with the iterate in place of ; dropping the nonnegative terms and gives .
Formalization Note The first equality holds for any two points of . The rewritten form uses that the second point is optimal (so and by Theorem 2 (iv)) and that ; these are exactly the hypotheses of the statement.
Preamble
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
Formal statement
namespace SelfDualLP.Output
/-- Proof of Theorem 8 (p. 63), orthogonality identity, under (7). Let `z = (y, x, τ, θ, s, κ) ∈ 𝓕_h`
and let `w = (y*, x*, τ*, θ*, s*, κ*)` be a self-complementary (optimal) solution of (HLP) with
`κ* = 0`. Then `(x − x*)ᵀ(s − s*) + (τ − τ*)(κ − κ*) = 0`, which can be rewritten as
`xᵀs* + sᵀx* + κτ* = (n + 1)μ = (n + 1)θ`, where `μ = (xᵀs + τκ)/(n + 1)`. -/
theorem orthogonality_identity {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (z w : HLPPoint m n) (hz : HLPFeasible7 A b c z)
(hw : HLPOptimal7 A b c w) (hκ : w.κ = 0) :
(z.x - w.x) ⬝ᵥ (z.s - w.s) + (z.τ - w.τ) * (z.κ - w.κ) = 0 ∧
z.x ⬝ᵥ w.s + z.s ⬝ᵥ w.x + z.κ * w.τ = ((n : ℝ) + 1) * mu z ∧
((n : ℝ) + 1) * mu z = ((n : ℝ) + 1) * z.θ := by sorry
end SelfDualLP.Output
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 63, proof of Theorem 8; DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.