Convex Analysis (Rockafellar, 1970) -- Chapter 03 -- Section 16 -- Part 5

section Chap03section Section16open scoped BigOperatorsopen scoped Pointwise

In the improper case, the conjugates are identically : ?m.1.

lemma section16_fenchelConjugate_precomp_eq_top_of_improper_of_exists_mem_ri {n m : Nat} (A : EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) (g : (Fin m ) EReal) (hg : ConvexFunction g) (hri : x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) g)) (hproper : ¬ ProperConvexFunctionOn (Set.univ : Set (Fin m )) g) : (fenchelConjugate n (fun x => g (A (WithLp.toLp 2 x) : Fin m )) = constPosInf n) (fenchelConjugate m g = constPosInf m) := by classical have hconv_on : ConvexFunctionOn (Set.univ : Set (Fin m )) g := by simpa [ConvexFunction] using hg have himproper : ImproperConvexFunctionOn (Set.univ : Set (Fin m )) g := hconv_on, hproper rcases hri with x0, hx0 have hxbot : g (A x0 : Fin m ) = ( : EReal) := improperConvexFunctionOn_eq_bot_on_ri_effectiveDomain (f := g) himproper (x := A x0) hx0 have hbot : x : Fin m , g x = ( : EReal) := (A x0 : Fin m ), hxbot have hbot_precomp : x : Fin n , g (A (WithLp.toLp 2 x) : Fin m ) = ( : EReal) := by refine WithLp.ofLp x0, ?_ simpa [WithLp.toLp_ofLp] using hxbot have hstar : fenchelConjugate m g = constPosInf m := by funext xStar apply le_antisymm · exact le_top · rcases hbot with x, hx have htop : ((x ⬝ᵥ xStar : ) : EReal) - g x = ( : EReal) := by simp [hx] have hmem : ( : EReal) Set.range (fun y : Fin m => ((y ⬝ᵥ xStar : ) : EReal) - g y) := by refine x, ?_ exact htop simpa [constPosInf, fenchelConjugate] using (le_sSup hmem) have hstar_precomp : fenchelConjugate n (fun x => g (A (WithLp.toLp 2 x) : Fin m )) = constPosInf n := by funext xStar apply le_antisymm · exact le_top · rcases hbot_precomp with x, hx have htop : ((x ⬝ᵥ xStar : ) : EReal) - g (A (WithLp.toLp 2 x) : Fin m ) = ( : EReal) := by simp [hx] have hmem : ( : EReal) Set.range (fun y : Fin n => ((y ⬝ᵥ xStar : ) : EReal) - g (A (WithLp.toLp 2 y) : Fin m )) := by refine x, ?_ exact htop simpa [constPosInf, fenchelConjugate] using (le_sSup hmem) exact hstar_precomp, hstar

Closure commutes with linear precomposition under a relative-interior preimage point.

lemma section16_convexFunctionClosure_precomp_eq_precomp_convexFunctionClosure_of_exists_mem_ri {n m : Nat} (A : EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) {g : (Fin m ) EReal} (hgproper : ProperConvexFunctionOn (Set.univ : Set (Fin m )) g) (hri : x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) g)) : convexFunctionClosure (fun x : Fin n => g (A (WithLp.toLp 2 x) : Fin m )) = fun x => convexFunctionClosure g (A (WithLp.toLp 2 x) : Fin m ) := by classical let e_n := (EuclideanSpace.equiv (𝕜 := ) (ι := Fin n)) let e_m := (EuclideanSpace.equiv (𝕜 := ) (ι := Fin m)) let A' : (Fin n ) →ₗ[] (Fin m ) := e_m.toLinearMap.comp (A.comp e_n.symm.toLinearMap) have hri' : x : Fin n , e_m.symm (A' x) euclideanRelativeInterior m (Set.image e_m.symm (effectiveDomain (Set.univ : Set (Fin m )) g)) := by rcases hri with x0, hx0 refine e_n x0, ?_ have himage : Set.image e_m.symm (effectiveDomain (Set.univ : Set (Fin m )) g) = e_m ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) g := by simpa using (ContinuousLinearEquiv.image_eq_preimage_symm (e := e_m.symm) (s := effectiveDomain (Set.univ : Set (Fin m )) g)) have hx0' : A x0 euclideanRelativeInterior m (Set.image e_m.symm (effectiveDomain (Set.univ : Set (Fin m )) g)) := by simpa [himage] using hx0 have hA' : e_m.symm (A' (e_n x0)) = A x0 := by simp [A', e_n, e_m] simpa [hA'] using hx0' have hmain := convexFunctionClosure_precomp_linearMap_eq (hgproper := hgproper) (A := A') hri' have hA' : x : Fin n , A' x = (A (WithLp.toLp 2 x) : Fin m ) := by intro x have htoLp : WithLp.toLp 2 (A (WithLp.toLp 2 x) : Fin m ) = A (WithLp.toLp 2 x) := by simp [WithLp.toLp_ofLp] calc A' x = e_m (A (WithLp.toLp 2 x)) := by simp [A', e_n, e_m] _ = e_m (WithLp.toLp 2 (A (WithLp.toLp 2 x) : Fin m )) := by simp [htoLp] _ = (A (WithLp.toLp 2 x) : Fin m ) := by simpa using (section16_euclideanSpace_equiv_toLp (x := (A (WithLp.toLp 2 x) : Fin m ))) simpa [hA'] using hmain

Closedness and attainment for the adjoint-image infimum under the Unknown identifier `ri`ri condition.

lemma section16_adjointImage_closed_and_attained_of_exists_mem_ri_effectiveDomain {n m : Nat} (A : EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) (g : (Fin m ) EReal) (hgproper : ProperConvexFunctionOn (Set.univ : Set (Fin m )) g) (hri : x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) g)) : let Aadj : EuclideanSpace (Fin m) →ₗ[] EuclideanSpace (Fin n) := ((LinearMap.adjoint : (EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) ≃ₗ⋆[] (EuclideanSpace (Fin m) →ₗ[] EuclideanSpace (Fin n))) A) let gStar : (Fin m ) EReal := fenchelConjugate m g let h : (Fin n ) EReal := fun xStar : Fin n => sInf ((fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) '' {yStar | Aadj yStar = WithLp.toLp 2 xStar}) (convexFunctionClosure h = h) xStar : Fin n , h xStar = yStar : EuclideanSpace (Fin m), Aadj yStar = WithLp.toLp 2 xStar gStar (yStar : Fin m ) = h xStar := by classical let Aadj : EuclideanSpace (Fin m) →ₗ[] EuclideanSpace (Fin n) := ((LinearMap.adjoint : (EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) ≃ₗ⋆[] (EuclideanSpace (Fin m) →ₗ[] EuclideanSpace (Fin n))) A) let gStar : (Fin m ) EReal := fenchelConjugate m g let h : (Fin n ) EReal := fun xStar : Fin n => sInf ((fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) '' {yStar | Aadj yStar = WithLp.toLp 2 xStar}) let h0_plus : (Fin m ) EReal := recessionFunction gStar let e_n := (EuclideanSpace.equiv (𝕜 := ) (ι := Fin n)) let e_m := (EuclideanSpace.equiv (𝕜 := ) (ι := Fin m)) let Aadj' : (Fin m ) →ₗ[] (Fin n ) := e_n.toLinearMap.comp (Aadj.comp e_m.symm.toLinearMap) have hAadj' : z : Fin m , Aadj' z = (Aadj (WithLp.toLp 2 z) : Fin n ) := by intro z have htoLp : WithLp.toLp 2 (Aadj (WithLp.toLp 2 z) : Fin n ) = Aadj (WithLp.toLp 2 z) := by simp [WithLp.toLp_ofLp] calc Aadj' z = e_n (Aadj (e_m.symm z)) := by simp [Aadj', e_n, e_m] _ = e_n (Aadj (WithLp.toLp 2 z)) := by simp [e_m] _ = e_n (WithLp.toLp 2 (Aadj (WithLp.toLp 2 z) : Fin n )) := by simp [htoLp] _ = (Aadj (WithLp.toLp 2 z) : Fin n ) := by simpa using (section16_euclideanSpace_equiv_toLp (x := (Aadj (WithLp.toLp 2 z) : Fin n ))) have hset : xStar : Fin n , {yStar : EuclideanSpace (Fin m) | Aadj yStar = WithLp.toLp 2 xStar} = {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar} := by intro xStar ext yStar constructor · intro hy have hy' := congrArg (fun z : EuclideanSpace (Fin n) => (z : Fin n )) hy simpa [WithLp.ofLp_toLp] using hy' · intro hy have hy' := congrArg (fun z : Fin n => (WithLp.toLp 2 z : EuclideanSpace (Fin n))) hy simpa [WithLp.toLp_ofLp] using hy' let Ah : (Fin n ) EReal := fun xStar : Fin n => sInf {z : EReal | yStar : Fin m , Aadj' yStar = xStar z = gStar yStar} have hAh : Ah = h := by funext xStar have hset' : {z : EReal | yStar : Fin m , Aadj' yStar = xStar z = gStar yStar} = {z : EReal | yStar : EuclideanSpace (Fin m), (Aadj yStar : Fin n ) = xStar z = gStar (yStar : Fin m )} := by ext z constructor · rintro yStar, hyA, rfl refine WithLp.toLp 2 yStar, ?_, ?_ · have hyA' : (Aadj (WithLp.toLp 2 yStar) : Fin n ) = xStar := by simpa [hAadj' yStar] using hyA exact hyA' · simp · rintro yStar, hyA, rfl have hyA' : (Aadj (WithLp.toLp 2 (yStar : Fin m )) : Fin n ) = xStar := by simpa [WithLp.toLp_ofLp] using hyA have hyA'' : Aadj' (yStar : Fin m ) = xStar := by simpa [hAadj' (yStar : Fin m )] using hyA' exact (yStar : Fin m ), hyA'', rfl have himage : sInf ((fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) '' {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar}) = sInf {z : EReal | yStar : EuclideanSpace (Fin m), (Aadj yStar : Fin n ) = xStar z = gStar (yStar : Fin m )} := by simpa using (section16_sInf_image_fiber_eq_sInf_exists (φ := fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) (S := {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar})) have hrewrite : h xStar = sInf ((fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) '' {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar}) := by simp [h, hset] calc Ah xStar = sInf {z : EReal | yStar : EuclideanSpace (Fin m), (Aadj yStar : Fin n ) = xStar z = gStar (yStar : Fin m )} := by simp [Ah, hset'] _ = sInf ((fun yStar : EuclideanSpace (Fin m) => gStar (yStar : Fin m )) '' {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar}) := by symm exact himage _ = h xStar := by symm exact hrewrite have hclosedStar : ClosedConvexFunction gStar := by have h := fenchelConjugate_closedConvex (n := m) (f := g) exact h.2, h.1 have hproperStar : ProperConvexFunctionOn (Set.univ : Set (Fin m )) gStar := proper_fenchelConjugate_of_proper (n := m) (f := g) hgproper have hsupp : supportFunctionEReal (effectiveDomain (Set.univ : Set (Fin m )) g) = h0_plus := by simpa [h0_plus, gStar, recessionFunction] using (supportFunctionEReal_effectiveDomain_eq_recession_fenchelConjugate (n := m) (f := g) (hf := hgproper) (fStar0_plus := h0_plus) (by intro y; rfl)) have hdom_ne : Set.Nonempty (effectiveDomain (Set.univ : Set (Fin m )) g) := section13_effectiveDomain_nonempty_of_proper (n := m) (f := g) hgproper have hdom_conv : Convex (effectiveDomain (Set.univ : Set (Fin m )) g) := by have hconv_on : ConvexFunctionOn (Set.univ : Set (Fin m )) g := hgproper.1 simpa using (effectiveDomain_convex (S := (Set.univ : Set (Fin m ))) (f := g) (hf := hconv_on)) have hsupp_props := section13_supportFunctionEReal_closedProperConvex_posHom (n := m) (C := effectiveDomain (Set.univ : Set (Fin m )) g) hdom_ne hdom_conv have hpos : PositivelyHomogeneous h0_plus := by simpa [hsupp] using hsupp_props.2.2 have hproper0 : ProperConvexFunctionOn (Set.univ : Set (Fin m )) h0_plus := by simpa [hsupp] using hsupp_props.2.1 have hrec : Set.recessionCone (epigraph (Set.univ : Set (Fin m )) gStar) = epigraph (Set.univ : Set (Fin m )) h0_plus := by let f : Fin 1 (Fin m ) EReal := fun _ => gStar have hconv : i : Fin 1, Convex (epigraph (Set.univ : Set (Fin m )) (f i)) := by intro i have hconvStar : ConvexFunctionOn (Set.univ : Set (Fin m )) gStar := by have hconv : ConvexFunction gStar := (fenchelConjugate_closedConvex (n := m) (f := g)).2 simpa [ConvexFunction] using hconv simpa [f] using (convex_epigraph_of_convexFunctionOn (hf := hconvStar)) have hproper : i : Fin 1, ProperConvexFunctionOn (Set.univ : Set (Fin m )) (f i) := by intro i simpa [f] using hproperStar have hk : (i : Fin 1) (y : Fin m ), h0_plus y = sSup { r : EReal | x : Fin m , r = f i (x + y) - f i x } := by intro i y simpa [f, h0_plus] using (section16_recessionFunction_eq_sSup_unrestricted (f := gStar) y) have hrec' := recessionCone_epigraph_eq_epigraph_k (f := f) (k := h0_plus) hconv hproper hk simpa [f] using hrec' (i := 0) have hno : ¬ yStar : EuclideanSpace (Fin m), Aadj yStar = 0 h0_plus (yStar : Fin m ) (0 : EReal) h0_plus (-yStar : Fin m ) > (0 : EReal) := by have hcorr := (section16_exists_image_mem_ri_effectiveDomain_iff_not_exists_adjoint_eq_zero_recession_ineq (A := A) (g := g) hgproper) have hno' : ¬ yStar : EuclideanSpace (Fin m), Aadj yStar = 0 recessionFunction (fenchelConjugate m g) (yStar : Fin m ) (0 : EReal) recessionFunction (fenchelConjugate m g) (-yStar : Fin m ) > (0 : EReal) := by exact (hcorr).mpr hri simpa [gStar, h0_plus] using hno' have hA' : z : Fin m , h0_plus z (0 : EReal) h0_plus (-z) > (0 : EReal) Aadj' z 0 := by intro z hzle hzgt hAz have hAz' : (Aadj (WithLp.toLp 2 z) : Fin n ) = 0 := by simpa [hAadj' z] using hAz have hAz'' : Aadj (WithLp.toLp 2 z) = 0 := by ext i simpa using congrArg (fun f => f i) hAz' apply hno refine WithLp.toLp 2 z, hAz'', ?_, ?_ · simpa [WithLp.ofLp_toLp] using hzle · simpa [WithLp.ofLp_toLp] using hzgt have hmain := linearMap_infimum_closed_proper_convex_recession (h := gStar) (h0_plus := h0_plus) hclosedStar hproperStar hrec hpos hproper0 (A := Aadj') hA' have hclosedAh : ClosedConvexFunction Ah := by simpa [Ah] using hmain.1 have hproperAh : ProperConvexFunctionOn (Set.univ : Set (Fin n )) Ah := by simpa [Ah] using hmain.2.1 have hnotbot : x : Fin n , Ah x ( : EReal) := by intro x exact hproperAh.2.2 x (by simp) have hclosureAh : convexFunctionClosure Ah = Ah := convexFunctionClosure_eq_of_closedConvexFunction (f := Ah) hclosedAh hnotbot have hclosure : convexFunctionClosure h = h := by simpa [hAh] using hclosureAh have hatt : xStar : Fin n , h xStar = yStar : EuclideanSpace (Fin m), Aadj yStar = WithLp.toLp 2 xStar gStar (yStar : Fin m ) = h xStar := by intro xStar have hAh_eq : Ah xStar = h xStar := by simpa using congrArg (fun f => f xStar) hAh have hatt' : Ah xStar = yStar : Fin m , Aadj' yStar = xStar gStar yStar = Ah xStar := by by_cases htop : Ah xStar = · exact Or.inl htop · rcases (hmain.2.2.2 xStar htop) with yStar, hyA, hyEq exact Or.inr yStar, hyA, hyEq.symm cases hatt' with | inl htop => left simpa [hAh_eq] using htop | inr hcase => rcases hcase with yStar, hyA, hyEq right have hyA' : Aadj (WithLp.toLp 2 yStar) = WithLp.toLp 2 xStar := by have hyA' : (Aadj (WithLp.toLp 2 yStar) : Fin n ) = xStar := by simpa [hAadj' yStar] using hyA have hyAset : (WithLp.toLp 2 yStar) {yStar : EuclideanSpace (Fin m) | (Aadj yStar : Fin n ) = xStar} := by simpa using hyA' have hyAset' : (WithLp.toLp 2 yStar) {yStar : EuclideanSpace (Fin m) | Aadj yStar = WithLp.toLp 2 xStar} := by simpa [hset xStar] using hyAset simpa using hyAset' have hyEq' : gStar (WithLp.toLp 2 yStar : Fin m ) = h xStar := by simpa [WithLp.ofLp_toLp, hAh_eq] using hyEq exact WithLp.toLp 2 yStar, hyA', hyEq' exact hclosure, hatt

Properness and Unknown identifier `ri`ri-compatibility for indicator functions under a feasible point.

lemma section16_properConvexFunctionOn_indicatorFunction_of_exists_mem_ri {n m : Nat} (A : EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) (D : Set (Fin m )) (hD : Convex D) (hri : x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' D)) : ProperConvexFunctionOn (Set.univ : Set (Fin m )) (indicatorFunction D) x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) (indicatorFunction D)) := by classical rcases hri with x0, hx0 have hx0_mem_pre : A x0 ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' D) := (euclideanRelativeInterior_subset_closure m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' D)).1 hx0 have hx0_mem : (A x0 : Fin m ) D := by simpa using hx0_mem_pre have hDne : D.Nonempty := (A x0 : Fin m ), hx0_mem have hproper : ProperConvexFunctionOn (Set.univ : Set (Fin m )) (indicatorFunction D) := properConvexFunctionOn_indicator_of_convex_of_nonempty (C := D) hD hDne have hri' : x : EuclideanSpace (Fin n), A x euclideanRelativeInterior m ((fun z : EuclideanSpace (Fin m) => (z : Fin m )) ⁻¹' effectiveDomain (Set.univ : Set (Fin m )) (indicatorFunction D)) := by refine x0, ?_ simpa [effectiveDomain_indicatorFunction_eq (C := D)] using hx0 exact hproper, hri'

Precomposition of an indicator is the indicator of a preimage set.

lemma section16_indicator_precomp_eq_indicator_preimage {n m : Nat} (A : EuclideanSpace (Fin n) →ₗ[] EuclideanSpace (Fin m)) (D : Set (Fin m )) : (fun x : Fin n => indicatorFunction D (A (WithLp.toLp 2 x) : Fin m )) = indicatorFunction (Set.preimage (fun x : Fin n => (A (WithLp.toLp 2 x) : Fin m )) D) := by funext x by_cases hx : (A (WithLp.toLp 2 x) : Fin m ) D · simp [indicatorFunction, hx, Set.mem_preimage] · simp [indicatorFunction, hx, Set.mem_preimage]
end Section16end Chap03