Equation (9): normalization of the homogeneous feasible set
ProvedSelfDualLP.Regularity.equation_9interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Under and , every feasible point of (HLP) satisfies
Here is the -dimensional all-ones vector, so and are sums of coordinates; may be zero.
The equality is the paper's normalization constraint written in terms of the nonnegative primal and slack fields. At an optimum with , it forces at least one of to be nonzero.
Preamble
import Definitions.Def_SelfDualLP_Regularity_HLP
Formal statement
namespace SelfDualLP.Regularity
/-- Ye--Todd--Mizuno (1994), equation (9), p. 58. -/
theorem equation_9 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ) (w : HLPPoint m n)
(hw : HLPFeasible A b c (fun _ => 1) (fun _ => 0) (fun _ => 1) w) :
(∑ j, w.x j) + (∑ j, w.s j) + w.τ + w.κ -
((n : ℝ) + 1) * w.θ = (n : ℝ) + 1 := 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. 58, equation (9); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.