Theorem 2(iv): zero optimal value and the complementarity identity
ProvedSelfDualLP.Regularity.theorem_2_ivinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
For arbitrary initial , , and , the homogeneous program (HLP) has an optimal point with objective value zero. At every feasible point ,
Because all terms on the right are nonnegative at feasible points, this identity also shows why an optimal point has and zero complementarity.
The identity connects the artificial objective with primal-dual complementarity and is used throughout the analysis of (HLP).
Preamble
import Definitions.Def_SelfDualLP_Regularity_HLP open Matrix
Formal statement
namespace SelfDualLP.Regularity
/-- Ye--Todd--Mizuno (1994), Theorem 2(iv), p. 57. -/
theorem theorem_2_iv {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ)
(x₀ : Fin n → ℝ) (y₀ : Fin m → ℝ) (s₀ : Fin n → ℝ)
(hx₀ : ∀ j, 0 < x₀ j) (hs₀ : ∀ j, 0 < s₀ j) :
(∃ w : HLPPoint m n,
IsHLPOptimal A b c x₀ y₀ s₀ w ∧ HLPObjective x₀ s₀ w = 0) ∧
∀ w : HLPPoint m n, HLPFeasible A b c x₀ y₀ s₀ w →
HLPObjective x₀ s₀ w = w.x ⬝ᵥ w.s + w.τ * w.κ := by sorry
end SelfDualLP.Regularity
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.