Proof of Theorem 8 — an optimal (LP)/(LD) pair, scaled by α = (n+1)/(eᵀx̄ + eᵀs̄ + 1), is a self-complementary solution of (HLP)
ProvedSelfDualLP.Output.optimal_pair_solutioninterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work with (HLP) under the choice (7). Let be an optimal solution of (LP) and an optimal solution of (LD) (with ). Put
Then , and the point
is a self-complementary (that is, optimal) solution of (HLP).
In the proof of Theorem 8 this solution is compared with the iterates; its component produces the lower bound on .
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): if `x̄` is optimal for (LP) and `(ȳ, s̄)` is optimal for (LD), then
with `α = (n + 1)/(eᵀx̄ + eᵀs̄ + 1) > 0` the point
`(y*, x*, τ*, θ*, s*, κ*) = (αȳ, αx̄, α, 0, αs̄, 0)` is a self-complementary (i.e. optimal)
solution of (HLP) under (7). -/
theorem optimal_pair_solution {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (xbar : Fin n → ℝ) (ybar : Fin m → ℝ) (sbar : Fin n → ℝ)
(hx : SelfDualLP.Complexity.LPOptimal A b c xbar) (hy : SelfDualLP.Complexity.LDOptimal A b c ybar sbar) :
0 < ((n : ℝ) + 1) / (ones n ⬝ᵥ xbar + ones n ⬝ᵥ sbar + 1) ∧
HLPOptimal7 A b c
(let α : ℝ := ((n : ℝ) + 1) / (ones n ⬝ᵥ xbar + ones n ⬝ᵥ sbar + 1)
⟨α • ybar, α • xbar, α, 0, α • sbar, 0⟩) := 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.