Separating hyperplane theorem
ProvedLinearOptimization.separating_hyperplane_polyhedronconvexitydualityseparation
(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 .
Preamble
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`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.11, p. 170