Theorem 22.1 — basic properties of homogeneous self-dual problems
ProvedVanderbeiLP.SelfDual.homogeneous_self_dual_propertieslinear-programmingp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1self-dual
Let and let be a real skew-symmetric matrix (). Consider the homogeneous self-dual problem (22.4)
Then:
- (22.4) has feasible solutions, and every feasible solution is optimal;
- the set of feasible solutions has empty interior: there is no feasible with and . In fact, every feasible satisfies
Part (2) says that a homogeneous self-dual problem has no central path, which is why the algorithm of §22.2 works with infeasible iterates.
Formalization Note "Empty interior" is read as in Chapter 17: no feasible point with every component of and strictly positive (the topological interior in is empty for trivial reasons, since the feasible set lies in the subspace ). Optimality is optimality for the zero objective . The hypothesis is the standing assumption of §22.2 (p. 325).
Preamble
import Mathlib import Definitions.Def_VanderbeiLP_SelfDual_HomogeneousSelfDual open Matrix
Formal statement
namespace VanderbeiLP.SelfDual
/-- Theorem 22.1 (Vanderbei, p. 325). For the homogeneous self-dual problem (22.4) with
skew-symmetric `A` (`n ≥ 2`, the standing assumption of §22.2):
(1) it has feasible solutions and every feasible solution is optimal;
(2) no feasible solution has `x > 0` and `z > 0` (the feasible set has empty interior);
in fact every feasible `(x, z)` has `zᵀx = 0`. -/
theorem homogeneous_self_dual_properties {n : ℕ} (hn : 2 ≤ n)
(A : Matrix (Fin n) (Fin n) ℝ) (hA : IsSkewSymmetric A) :
((∃ x z : Fin n → ℝ, SelfDualFeasible A x z) ∧
∀ x z : Fin n → ℝ, SelfDualFeasible A x z → SelfDualOptimal A x z) ∧
((¬ ∃ x z : Fin n → ℝ, SelfDualFeasible A x z ∧ (∀ j, 0 < x j) ∧ ∀ j, 0 < z j) ∧
∀ x z : Fin n → ℝ, SelfDualFeasible A x z → z ⬝ᵥ x = 0) := by sorry
end VanderbeiLP.SelfDual
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 325, Theorem 22.1 (PDF p. 331); standing assumptions n ≥ 2, A = −Aᵀ on p. 325
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.