Theorem 2.5 — projection via extreme rays
ProvedDisjunctive.Polarity.projection_extreme_raysThis is Theorem 2.5 of Balas's Disjunctive Programming: the classical projection formula, foundational to the whole chapter's projection track.
Let and let be its projection cone. Then
That is, projecting out the -variables amounts to premultiplying the system by every extreme ray of the projection cone — a Fourier-Motzkin-style elimination stated once for an arbitrary polyhedron , from which the chapter's later results (integrality, dimension, and facet behavior under projection) all follow.
Formalization Note. IsExtremeRay requires the ray to be nonzero and its ray-set to be an
extreme subset of (Mathlib's IsExtreme), matching the classical notion of an extreme ray of
a pointed polyhedral cone.
import Mathlib import Definitions.Def_Disjunctive_Polarity_Projection
namespace Disjunctive.Polarity
/-- Theorem 2.5 (Balas §2.2, p. 27): the projection of `Q` onto the `x`-space is cut out by the
inequalities `(vB)x ≤ vb` for `v` ranging over the extreme rays of the projection cone `W`. -/
theorem projection_extreme_rays {m p q : ℕ} (A : Matrix (Fin m) (Fin p) ℝ)
(B : Matrix (Fin m) (Fin q) ℝ) (b : Fin m → ℝ) :
ProjOntoX (Poly2 A B b) =
{x : Fin q → ℝ | ∀ v, IsExtremeRay (ProjectionCone A) v →
dotProduct (Matrix.vecMul v B) x ≤ dotProduct v b} := by sorry
end Disjunctive.Polarity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.