Remark 7.5, p. 14 โ if ๐ด โ [0, 1]แต, every point of ๐ด โฉ {0, 1}แต is an extreme point of ๐ด
ProvedShortestGCS.Relax.remark_7_5binary-pointsextreme-pointsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reformulation-linearization
Let . Then every whose coordinates all lie in is an extreme point of :
Combined with Lemma 7.4 this says that the relaxation is exact at all binary points of such a , which is the setting of the first-level Reformulation-Linearization Technique for mixed-binary bilinear programs.
Formalization Note Only the first clause of the remark is stated; its second clause is Lemma 7.4 at these points. No convexity of is needed.
Preamble
import Mathlib import Definitions.Def_ShortestGCS_MICP_Perspective import Definitions.Def_ShortestGCS_Relax_Setting
Formal statement
namespace ShortestGCS.Relax
/-- Remark 7.5, arXiv:2101.11565v5, p. 14: if `๐ด โ [0, 1]แต`, every `y โ ๐ด โฉ {0, 1}แต` is an extreme point of
`๐ด`. -/
theorem remark_7_5 {m : โ} (Y : Set (Fin m โ โ)) (hY : Y โ {y | โ i, y i โ Set.Icc (0 : โ) 1}) :
โ y โ Y, (โ i, y i = 0 โจ y i = 1) โ y โ Set.extremePoints โ Y := by sorry
end ShortestGCS.Relax
Source
arXiv:2101.11565v5, Remark 7.5, p. 14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.