Proposition 6.4.2 — the Farkas lemma geometrically
ProvedMatousekLP.Duality.farkas_geometricconvex-geometryfarkas-lemmap2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be vectors in and let be the convex cone they generate. Then exactly one of the following occurs:
- (F1') ;
- (F2') there is with
that is, the hyperplane through the origin has all of (and hence ) on one side and strictly on the other.
This is the separation-theorem reading of the Farkas lemma: a point outside a finitely generated cone can be separated from it by a hyperplane through the origin.
Formalization Note Points are elements of EuclideanSpace ℝ (Fin m) and is the inner product inner ℝ y x. "Exactly one" is Lean's exclusive or Xor.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Duality_Cones
Formal statement
namespace MatousekLP.Duality
/-- Matoušek & Gärtner, Proposition 6.4.2 (pp. 89–90), the Farkas lemma geometrically: for
`a₁, …, aₙ, b ∈ ℝ^m` exactly one of (F1') `b` lies in the convex cone `C` generated by
`a₁, …, aₙ`, and (F2') there is `y ∈ ℝ^m` with `yᵀaᵢ ≥ 0` for all `i` and `yᵀb < 0` (the
hyperplane `{x : yᵀx = 0}` through `0` has `C` on one side and `b` strictly on the other). -/
theorem farkas_geometric {m n : ℕ} (a : Fin n → EuclideanSpace ℝ (Fin m))
(b : EuclideanSpace ℝ (Fin m)) :
Xor (b ∈ coneGen a)
(∃ y : EuclideanSpace ℝ (Fin m), (∀ i, 0 ≤ inner ℝ y (a i)) ∧ inner ℝ y b < 0) := by sorry
end MatousekLP.Duality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, pp. 89–90, Proposition 6.4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.