🏛️ Atlas✒️Isabelle.MemoryAccessFloors.Inf_Affine_Concave view on GitHub ↗3 theorems
(*  Title:      Inf_Affine_Concave.thy    Author:     Carles Marin    Copyright:  Carles Marin    License:    BSD-3-Clause     The infimum of a family of affine functions with non-negative slopes is non-decreasing and concave.*) theory Inf_Affine_Concave  imports "HOL-Analysis.Analysis"begin definition inf_affine :: "'a set \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> real \<Rightarrow> real"  where "inf_affine I \<alpha> \<beta> r = Inf ((\<lambda>i. \<alpha> i + \<beta> i * r) ` I)" lemma inf_affine_le:  assumes "bdd_below ((\<lambda>i. \<alpha> i + \<beta> i * r) ` I)" "i \<in> I"  shows "inf_affine I \<alpha> \<beta> r \<le> \<alpha> i + \<beta> i * r"  unfolding inf_affine_def using assms by (intro cInf_lower) simp_all lemma inf_affine_monotone:  assumes "I \<noteq> {}" "\<forall>i\<in>I. 0 \<le> \<beta> i"    "\<forall>r\<ge>0. bdd_below ((\<lambda>i. \<alpha> i + \<beta> i * r) ` I)"  shows "monotone_on {0..} (\<le>) (\<le>) (inf_affine I \<alpha> \<beta>)"proof (rule monotone_onI)  fix r s :: real  assume rs: "r \<in> {0..}" "s \<in> {0..}" "r \<le> s"  have "\<forall>i\<in>I. inf_affine I \<alpha> \<beta> r \<le> \<alpha> i + \<beta> i * s"  proof    fix i assume i: "i \<in> I"    have "inf_affine I \<alpha> \<beta> r \<le> \<alpha> i + \<beta> i * r"      using inf_affine_le[where r = r and i = i] assms(3) rs(1) i by simp    moreover have "\<beta> i * r \<le> \<beta> i * s" using assms(2) i rs(3) by (simp add: mult_left_mono)    ultimately show "inf_affine I \<alpha> \<beta> r \<le> \<alpha> i + \<beta> i * s" by linarith  qed  then show "inf_affine I \<alpha> \<beta> r \<le> inf_affine I \<alpha> \<beta> s"    unfolding inf_affine_def using assms(1) by (intro cInf_greatest) autoqed lemma inf_affine_concave:  assumes "I \<noteq> {}" "\<forall>r\<ge>0. bdd_below ((\<lambda>i. \<alpha> i + \<beta> i * r) ` I)"  shows "concave_on {0..} (inf_affine I \<alpha> \<beta>)"proof (rule concave_on_linorderI)  fix r s t :: real  assume t: "0 < t" "t < 1" and rs: "r \<in> {0..}" "s \<in> {0..}" "r < s"  have "\<forall>i\<in>I. (1 - t) * inf_affine I \<alpha> \<beta> r + t * inf_affine I \<alpha> \<beta> s                \<le> \<alpha> i + \<beta> i * ((1 - t) *\<^sub>R r + t *\<^sub>R s)"  proof    fix i assume i: "i \<in> I"    have a: "inf_affine I \<alpha> \<beta> r \<le> \<alpha> i + \<beta> i * r"      using inf_affine_le[where r = r and i = i] assms(2) rs(1) i by simp    have b: "inf_affine I \<alpha> \<beta> s \<le> \<alpha> i + \<beta> i * s"      using inf_affine_le[where r = s and i = i] assms(2) rs(2) i by simp    have "(1 - t) * inf_affine I \<alpha> \<beta> r + t * inf_affine I \<alpha> \<beta> s          \<le> (1 - t) * (\<alpha> i + \<beta> i * r) + t * (\<alpha> i + \<beta> i * s)"      using a b t by (intro add_mono mult_left_mono) simp_all    also have "\<dots> = \<alpha> i + \<beta> i * ((1 - t) *\<^sub>R r + t *\<^sub>R s)" by (simp add: real_scaleR_def algebra_simps)    finally show "(1 - t) * inf_affine I \<alpha> \<beta> r + t * inf_affine I \<alpha> \<beta> s                  \<le> \<alpha> i + \<beta> i * ((1 - t) *\<^sub>R r + t *\<^sub>R s)" .  qed  then show "(1 - t) * inf_affine I \<alpha> \<beta> r + t * inf_affine I \<alpha> \<beta> s             \<le> inf_affine I \<alpha> \<beta> ((1 - t) *\<^sub>R r + t *\<^sub>R s)"    unfolding inf_affine_def using assms(1) by (intro cInf_greatest) autoqed (simp add: convex_real_interval) end