src/HOL/Multivariate_Analysis/Polytope.thy
changeset 63145 703edebd1d92
parent 63078 e49dc94eb624
child 63148 6a767355d1a9
equal deleted inserted replaced
63143:ef72b104fa32 63145:703edebd1d92
    97       using \<open>y \<noteq> x\<close> \<open>e > 0\<close> by simp
    97       using \<open>y \<noteq> x\<close> \<open>e > 0\<close> by simp
    98     show ?thesis
    98     show ?thesis
    99       apply (rule zne [OF in01])
    99       apply (rule zne [OF in01])
   100       apply (rule e [THEN subsetD])
   100       apply (rule e [THEN subsetD])
   101       apply (rule IntI)
   101       apply (rule IntI)
   102         using `y \<noteq> x` \<open>e > 0\<close>
   102         using \<open>y \<noteq> x\<close> \<open>e > 0\<close>
   103         apply (simp add: cball_def dist_norm algebra_simps)
   103         apply (simp add: cball_def dist_norm algebra_simps)
   104         apply (simp add: Real_Vector_Spaces.scaleR_diff_right [symmetric] norm_minus_commute min_mult_distrib_right)
   104         apply (simp add: Real_Vector_Spaces.scaleR_diff_right [symmetric] norm_minus_commute min_mult_distrib_right)
   105       apply (rule mem_affine [OF affine_affine_hull _ x])
   105       apply (rule mem_affine [OF affine_affine_hull _ x])
   106       using \<open>y \<in> T\<close>  apply (auto simp: hull_inc)
   106       using \<open>y \<in> T\<close>  apply (auto simp: hull_inc)
   107       done
   107       done
   206       using False nbc \<open>0 < e\<close>
   206       using False nbc \<open>0 < e\<close>
   207       apply (auto simp: algebra_simps)
   207       apply (auto simp: algebra_simps)
   208       done
   208       done
   209     then have "d \<in> T \<and> c \<in> T"
   209     then have "d \<in> T \<and> c \<in> T"
   210       apply (rule face_ofD [OF \<open>T face_of S\<close>])
   210       apply (rule face_ofD [OF \<open>T face_of S\<close>])
   211       using `d \<in> u`  `c \<in> u` \<open>u \<subseteq> S\<close>  \<open>b \<in> T\<close>  apply auto
   211       using \<open>d \<in> u\<close>  \<open>c \<in> u\<close> \<open>u \<subseteq> S\<close>  \<open>b \<in> T\<close>  apply auto
   212       done
   212       done
   213     then show ?thesis ..
   213     then show ?thesis ..
   214   qed
   214   qed
   215 qed
   215 qed
   216 
   216 
   336         then have "setsum c T = 0"
   336         then have "setsum c T = 0"
   337           by (simp add: S k_def setsum_diff sumc1)
   337           by (simp add: S k_def setsum_diff sumc1)
   338         then have [simp]: "setsum c (S - T) = 1"
   338         then have [simp]: "setsum c (S - T) = 1"
   339           by (simp add: S setsum_diff sumc1)
   339           by (simp add: S setsum_diff sumc1)
   340         have ci0: "\<And>i. i \<in> T \<Longrightarrow> c i = 0"
   340         have ci0: "\<And>i. i \<in> T \<Longrightarrow> c i = 0"
   341           by (meson `finite T` `setsum c T = 0` \<open>T \<subseteq> S\<close> cge0 setsum_nonneg_eq_0_iff subsetCE)
   341           by (meson \<open>finite T\<close> \<open>setsum c T = 0\<close> \<open>T \<subseteq> S\<close> cge0 setsum_nonneg_eq_0_iff subsetCE)
   342         then have [simp]: "(\<Sum>i\<in>S-T. c i *\<^sub>R i) = w"
   342         then have [simp]: "(\<Sum>i\<in>S-T. c i *\<^sub>R i) = w"
   343           by (simp add: weq_sumsum)
   343           by (simp add: weq_sumsum)
   344         have "w \<in> convex hull (S - T)"
   344         have "w \<in> convex hull (S - T)"
   345           apply (simp add: convex_hull_finite fin)
   345           apply (simp add: convex_hull_finite fin)
   346           apply (rule_tac x=c in exI)
   346           apply (rule_tac x=c in exI)
   357           apply (rule_tac x="\<lambda>i. inverse (1-k) * c i" in exI)
   357           apply (rule_tac x="\<lambda>i. inverse (1-k) * c i" in exI)
   358           apply auto
   358           apply auto
   359           apply (metis sumcf cge0 inverse_nonnegative_iff_nonnegative mult_nonneg_nonneg S(2) setsum_nonneg subsetCE)
   359           apply (metis sumcf cge0 inverse_nonnegative_iff_nonnegative mult_nonneg_nonneg S(2) setsum_nonneg subsetCE)
   360           apply (metis False mult.commute right_inverse right_minus_eq setsum_right_distrib sumcf)
   360           apply (metis False mult.commute right_inverse right_minus_eq setsum_right_distrib sumcf)
   361           by (metis (mono_tags, lifting) scaleR_right.setsum scaleR_scaleR setsum.cong)
   361           by (metis (mono_tags, lifting) scaleR_right.setsum scaleR_scaleR setsum.cong)
   362         with `0 < k`  have "inverse(k) *\<^sub>R (w - setsum (\<lambda>i. c i *\<^sub>R i) T) \<in> affine hull T"
   362         with \<open>0 < k\<close>  have "inverse(k) *\<^sub>R (w - setsum (\<lambda>i. c i *\<^sub>R i) T) \<in> affine hull T"
   363           by (simp add: affine_diff_divide [OF affine_affine_hull] False waff convex_hull_subset_affine_hull [THEN subsetD])
   363           by (simp add: affine_diff_divide [OF affine_affine_hull] False waff convex_hull_subset_affine_hull [THEN subsetD])
   364         moreover have "inverse(k) *\<^sub>R (w - setsum (\<lambda>x. c x *\<^sub>R x) T) \<in> convex hull (S - T)"
   364         moreover have "inverse(k) *\<^sub>R (w - setsum (\<lambda>x. c x *\<^sub>R x) T) \<in> convex hull (S - T)"
   365           apply (simp add: weq_sumsum convex_hull_finite fin)
   365           apply (simp add: weq_sumsum convex_hull_finite fin)
   366           apply (rule_tac x="\<lambda>i. inverse k * c i" in exI)
   366           apply (rule_tac x="\<lambda>i. inverse k * c i" in exI)
   367           using \<open>k > 0\<close> cge0
   367           using \<open>k > 0\<close> cge0
   411       ultimately show ?thesis
   411       ultimately show ?thesis
   412         by (rule face_ofD [OF \<open>T face_of S\<close>, THEN conjunct2])
   412         by (rule face_ofD [OF \<open>T face_of S\<close>, THEN conjunct2])
   413     qed
   413     qed
   414   qed
   414   qed
   415   then show False
   415   then show False
   416     using `T \<noteq> S` \<open>T face_of S\<close> face_of_imp_subset by blast
   416     using \<open>T \<noteq> S\<close> \<open>T face_of S\<close> face_of_imp_subset by blast
   417 qed
   417 qed
   418 
   418 
   419 
   419 
   420 lemma face_of_affine_eq:
   420 lemma face_of_affine_eq:
   421    "affine S \<Longrightarrow> (T face_of S \<longleftrightarrow> T = {} \<or> T = S)"
   421    "affine S \<Longrightarrow> (T face_of S \<longleftrightarrow> T = {} \<or> T = S)"
  2502 proof -
  2502 proof -
  2503   have "finite S" by (metis assms aff_independent_finite)
  2503   have "finite S" by (metis assms aff_independent_finite)
  2504   then consider "card S = 0" | "card S = 1" | "2 \<le> card S" by arith
  2504   then consider "card S = 0" | "card S = 1" | "2 \<le> card S" by arith
  2505   then show ?thesis
  2505   then show ?thesis
  2506   proof cases
  2506   proof cases
  2507     case 1 then have "S = {}" by (simp add: `finite S`)
  2507     case 1 then have "S = {}" by (simp add: \<open>finite S\<close>)
  2508     then show ?thesis by simp
  2508     then show ?thesis by simp
  2509   next
  2509   next
  2510     case 2 show ?thesis
  2510     case 2 show ?thesis
  2511       by (auto intro: card_1_singletonE [OF `card S = 1`])
  2511       by (auto intro: card_1_singletonE [OF \<open>card S = 1\<close>])
  2512   next
  2512   next
  2513     case 3
  2513     case 3
  2514     with assms show ?thesis
  2514     with assms show ?thesis
  2515       by (auto simp: polyhedron_convex_hull rel_boundary_of_polyhedron facet_of_convex_hull_affine_independent_alt \<open>finite S\<close>)
  2515       by (auto simp: polyhedron_convex_hull rel_boundary_of_polyhedron facet_of_convex_hull_affine_independent_alt \<open>finite S\<close>)
  2516   qed
  2516   qed
  2533       then obtain a where "a \<in> S" "a \<notin> T"
  2533       then obtain a where "a \<in> S" "a \<notin> T"
  2534         using \<open>T \<subseteq> S\<close> by blast
  2534         using \<open>T \<subseteq> S\<close> by blast
  2535       then have "x \<in> (\<Union>a\<in>S. convex hull (S - {a}))"
  2535       then have "x \<in> (\<Union>a\<in>S. convex hull (S - {a}))"
  2536         using True affine_independent_iff_card [of S]
  2536         using True affine_independent_iff_card [of S]
  2537         apply simp
  2537         apply simp
  2538         apply (metis (no_types, hide_lams) Diff_eq_empty_iff Diff_insert0 `a \<notin> T` `T \<subseteq> S` `x \<in> convex hull T`  hull_mono insert_Diff_single   subsetCE)
  2538         apply (metis (no_types, hide_lams) Diff_eq_empty_iff Diff_insert0 \<open>a \<notin> T\<close> \<open>T \<subseteq> S\<close> \<open>x \<in> convex hull T\<close>  hull_mono insert_Diff_single   subsetCE)
  2539         done
  2539         done
  2540     } note * = this
  2540     } note * = this
  2541     have 1: "convex hull S \<subseteq> (\<Union> a\<in>S. convex hull (S - {a}))"
  2541     have 1: "convex hull S \<subseteq> (\<Union> a\<in>S. convex hull (S - {a}))"
  2542       apply (subst caratheodory_aff_dim)
  2542       apply (subst caratheodory_aff_dim)
  2543       apply (blast intro: *)
  2543       apply (blast intro: *)