Theorem 2 (iv) — the optimal value of (HLP) is zero and ((x⁰)ᵀs⁰ + 1)θ = xᵀs + τκ on F_h
ProvedSelfDualLP.Output.theorem_2_ivinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Let , , , and let , (componentwise) and be arbitrary. Consider the homogeneous self-dual program (HLP) built from these data. Then:
- the optimal value of (HLP) is zero, i.e. (HLP) has an optimal solution and its objective value is ;
- every feasible point satisfies
Under the choice (7) the identity reads , i.e. on ; in particular every optimal solution has .
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
/-- Theorem 2 (iv) (p. 57). For any `x⁰ > 0`, `s⁰ > 0` and `y⁰`: the optimal value of (HLP) is
zero (there is an optimal solution and its objective value `((x⁰)ᵀs⁰ + 1)θ` is `0`), and every
feasible point `(y, x, τ, θ, s, κ) ∈ 𝓕_h` satisfies `((x⁰)ᵀs⁰ + 1)θ = xᵀs + τκ`. -/
theorem theorem_2_iv {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x0 : Fin n → ℝ) (y0 : Fin m → ℝ) (s0 : Fin n → ℝ)
(hx0 : ∀ j, 0 < x0 j) (hs0 : ∀ j, 0 < s0 j) :
(∃ z : HLPPoint m n, HLPOptimal A b c x0 y0 s0 z ∧ hlpObjective x0 s0 z = 0) ∧
∀ z : HLPPoint m n, HLPFeasible A b c x0 y0 s0 z →
(x0 ⬝ᵥ s0 + 1) * z.θ = z.x ⬝ᵥ z.s + z.τ * 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. 57, Theorem 2 (iv); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.