Separating hyperplane theorem
ProvedLinearOptimization.separating_hyperplane_polyhedron(Theorem 4.11, separating hyperplane theorem) Let be a nonempty closed convex subset of and let be a vector that does not belong to . Then, there exists some vector such that
for all .
import Mathlib.Topology.MetricSpace.Basic import Mathlib.Analysis.Convex.Basic import Mathlib.Data.Matrix.Mul open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.11 (p. 170).** Separating hyperplane theorem: for a nonempty closed convex `S ⊆ ℝⁿ` and `x* ∉ S` there is a vector `c` with `c'x* < c'x` for every `x ∈ S`. -/
theorem LinearOptimization.separating_hyperplane_polyhedron {n : ℕ} (S : Set (Fin n → ℝ))
(hS : S.Nonempty) (hclosed : IsClosed S) (hconv : Convex ℝ S)
(xstar : Fin n → ℝ) (hx : xstar ∉ S) :
∃ c : Fin n → ℝ, ∀ x ∈ S, c ⬝ᵥ xstar < c ⬝ᵥ x := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For every , every subset that is nonempty, closed, and convex (over ), and every point with : there exists a vector such that for every (strict inequality, pointwise in ). Despite the theorem's name, no polyhedral structure is assumed — is an arbitrary nonempty closed convex set. The vector is not asserted to be nonzero or normalized (though could not satisfy the strict inequality since is nonempty), and no uniform gap is asserted: the statement does not claim , only strict inequality at each individual . For the hypotheses are unsatisfiable ( is a one-point space, so a nonempty contains every point), making the statement vacuous there.
Confirmed by the mission captain (proposal self-audit).