Lemma 6.5.1 — a finitely generated cone has a point nearest to b
ProvedMatousekLP.Duality.exists_nearest_point_coneconesconvex-geometryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be the convex cone generated by finitely many vectors , and let be a point with . Then there is a point nearest to in the Euclidean distance:
The nearest point is used to build the separating vector in the analytic proof of the geometric Farkas lemma (Proposition 6.4.2). The existence of is not automatic, since a nearest point need not exist in a set that is not closed.
Formalization Note is EuclideanSpace ℝ (Fin m), whose norm is the Euclidean norm.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Duality_Cones
Formal statement
namespace MatousekLP.Duality
/-- Matoušek & Gärtner, Lemma 6.5.1 (p. 95): if `C` is the convex cone in `ℝ^m` generated by
finitely many vectors `a₁, …, aₙ` and `b ∉ C`, then some `z ∈ C` is nearest to `b` in the
Euclidean distance: `‖z - b‖ ≤ ‖x - b‖` for all `x ∈ C`. -/
theorem exists_nearest_point_cone {m n : ℕ} (a : Fin n → EuclideanSpace ℝ (Fin m))
(b : EuclideanSpace ℝ (Fin m)) (hb : b ∉ coneGen a) :
∃ z ∈ coneGen a, ∀ x ∈ coneGen a, ‖z - b‖ ≤ ‖x - b‖ := by sorry
end MatousekLP.Duality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 95, Lemma 6.5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.