Jensen's inequality and maximum principle for convex functions

In this file, we prove the finite Jensen inequality and the finite maximum principle for convex functions. The integral versions are to be found in Analysis.Convex.Integral.

Main declarations

Jensen's inequalities:

• ConvexOn.map_centerMass_le, ConvexOn.map_sum_le: Convex Jensen's inequality. The image of a convex combination of points under a convex function is less than the convex combination of the images.
• ConcaveOn.le_map_centerMass, ConcaveOn.le_map_sum: Concave Jensen's inequality.
• StrictConvexOn.map_sum_lt: Convex strict Jensen inequality.
• StrictConcaveOn.lt_map_sum: Concave strict Jensen inequality.

As corollaries, we get:

• StrictConvexOn.map_sum_eq_iff: Equality case of the convex Jensen inequality.
• StrictConcaveOn.map_sum_eq_iff: Equality case of the concave Jensen inequality.
• ConvexOn.exists_ge_of_mem_convexHull: Maximum principle for convex functions.
• ConcaveOn.exists_le_of_mem_convexHull: Minimum principle for concave functions.

Jensen's inequality

theorem ConvexOn.map_centerMass_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : ConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : 0 < Finset.sum t fun (i : ι) => w i) (hmem : ∀ i ∈ t, p i ∈ s) : f (Finset.centerMass t w p) ≤ Finset.centerMass t w (f ∘ p)

Convex Jensen's inequality, Finset.centerMass version.

theorem ConcaveOn.le_map_centerMass {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : ConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : 0 < Finset.sum t fun (i : ι) => w i) (hmem : ∀ i ∈ t, p i ∈ s) : Finset.centerMass t w (f ∘ p) ≤ f (Finset.centerMass t w p)

Concave Jensen's inequality, Finset.centerMass version.

theorem ConvexOn.map_sum_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : ConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : f (Finset.sum t fun (i : ι) => w i • p i) ≤ Finset.sum t fun (i : ι) => w i • f (p i)

Convex Jensen's inequality, Finset.sum version.

theorem ConcaveOn.le_map_sum {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : ConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : (Finset.sum t fun (i : ι) => w i • f (p i)) ≤ f (Finset.sum t fun (i : ι) => w i • p i)

Concave Jensen's inequality, Finset.sum version.

theorem ConvexOn.map_add_sum_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} {v : 𝕜} {q : E} (hf : ConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (v + Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (hv : 0 ≤ v) (hq : q ∈ s) : f (v • q + Finset.sum t fun (i : ι) => w i • p i) ≤ v • f q + Finset.sum t fun (i : ι) => w i • f (p i)

Convex Jensen's inequality where an element plays a distinguished role.

theorem ConcaveOn.map_add_sum_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} {v : 𝕜} {q : E} (hf : ConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (v + Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (hv : 0 ≤ v) (hq : q ∈ s) : (v • f q + Finset.sum t fun (i : ι) => w i • f (p i)) ≤ f (v • q + Finset.sum t fun (i : ι) => w i • p i)

Concave Jensen's inequality where an element plays a distinguished role.

Strict Jensen inequality

theorem StrictConvexOn.map_sum_lt {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (hp : ∃ j ∈ t, ∃ k ∈ t, p j ≠ p k) : f (Finset.sum t fun (i : ι) => w i • p i) < Finset.sum t fun (i : ι) => w i • f (p i)

Convex strict Jensen inequality.

If the function is strictly convex, the weights are strictly positive and the indexed family of points is non-constant, then Jensen's inequality is strict.

See also StrictConvexOn.map_sum_eq_iff.

theorem StrictConcaveOn.lt_map_sum {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (hp : ∃ j ∈ t, ∃ k ∈ t, p j ≠ p k) : (Finset.sum t fun (i : ι) => w i • f (p i)) < f (Finset.sum t fun (i : ι) => w i • p i)

Concave strict Jensen inequality.

If the function is strictly concave, the weights are strictly positive and the indexed family of points is non-constant, then Jensen's inequality is strict.

See also StrictConcaveOn.map_sum_eq_iff.

Equality case of Jensen's inequality

theorem StrictConvexOn.eq_of_le_map_sum {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (h_eq : (Finset.sum t fun (i : ι) => w i • f (p i)) ≤ f (Finset.sum t fun (i : ι) => w i • p i)) ⦃j : ι⦄ : j ∈ t → ∀ ⦃k : ι⦄, k ∈ t → p j = p k

A form of the equality case of Jensen's equality.

For a strictly convex function f and positive weights w, if f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i), then the points p are all equal.

See also StrictConvexOn.map_sum_eq_iff.

theorem StrictConcaveOn.eq_of_map_sum_eq {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) (h_eq : f (Finset.sum t fun (i : ι) => w i • p i) ≤ Finset.sum t fun (i : ι) => w i • f (p i)) ⦃j : ι⦄ : j ∈ t → ∀ ⦃k : ι⦄, k ∈ t → p j = p k

A form of the equality case of Jensen's equality.

For a strictly concave function f and positive weights w, if f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i), then the points p are all equal.

See also StrictConcaveOn.map_sum_eq_iff.

theorem StrictConvexOn.map_sum_eq_iff {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : (f (Finset.sum t fun (i : ι) => w i • p i) = Finset.sum t fun (i : ι) => w i • f (p i)) ↔ ∀ j ∈ t, p j = Finset.sum t fun (i : ι) => w i • p i

Canonical form of the equality case of Jensen's equality.

For a strictly convex function f and positive weights w, we have f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i) if and only if the points p are all equal (and in fact all equal to their center of mass wrt w).

theorem StrictConcaveOn.map_sum_eq_iff {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 < w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : (f (Finset.sum t fun (i : ι) => w i • p i) = Finset.sum t fun (i : ι) => w i • f (p i)) ↔ ∀ j ∈ t, p j = Finset.sum t fun (i : ι) => w i • p i

Canonical form of the equality case of Jensen's equality.

For a strictly concave function f and positive weights w, we have f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i) if and only if the points p are all equal (and in fact all equal to their center of mass wrt w).

theorem StrictConvexOn.map_sum_eq_iff' {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConvexOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : (f (Finset.sum t fun (i : ι) => w i • p i) = Finset.sum t fun (i : ι) => w i • f (p i)) ↔ ∀ j ∈ t, w j ≠ 0 → p j = Finset.sum t fun (i : ι) => w i • p i

Canonical form of the equality case of Jensen's equality.

For a strictly convex function f and nonnegative weights w, we have f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i) if and only if the points p with nonzero weight are all equal (and in fact all equal to their center of mass wrt w).

theorem StrictConcaveOn.map_sum_eq_iff' {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [OrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (hf : StrictConcaveOn 𝕜 s f) (h₀ : ∀ i ∈ t, 0 ≤ w i) (h₁ : (Finset.sum t fun (i : ι) => w i) = 1) (hmem : ∀ i ∈ t, p i ∈ s) : (f (Finset.sum t fun (i : ι) => w i • p i) = Finset.sum t fun (i : ι) => w i • f (p i)) ↔ ∀ j ∈ t, w j ≠ 0 → p j = Finset.sum t fun (i : ι) => w i • p i

Canonical form of the equality case of Jensen's equality.

For a strictly concave function f and nonnegative weights w, we have f (∑ i in t, w i • p i) = ∑ i in t, w i • f (p i) if and only if the points p with nonzero weight are all equal (and in fact all equal to their center of mass wrt w).

Maximum principle

theorem le_sup_of_mem_convexHull {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : E → β} {x : E} {s : Finset E} (hf : ConvexOn 𝕜 ((convexHull 𝕜) ↑s) f) (hx : x ∈ (convexHull 𝕜) ↑s) : f x ≤ Finset.sup' s ⋯ f

theorem inf_le_of_mem_convexHull {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : E → β} {x : E} {s : Finset E} (hf : ConcaveOn 𝕜 ((convexHull 𝕜) ↑s) f) (hx : x ∈ (convexHull 𝕜) ↑s) : Finset.inf' s ⋯ f ≤ f x

theorem ConvexOn.exists_ge_of_centerMass {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (h : ConvexOn 𝕜 s f) (hw₀ : ∀ i ∈ t, 0 ≤ w i) (hw₁ : 0 < Finset.sum t fun (i : ι) => w i) (hp : ∀ i ∈ t, p i ∈ s) : ∃ i ∈ t, f (Finset.centerMass t w p) ≤ f (p i)

If a function f is convex on s, then the value it takes at some center of mass of points of s is less than the value it takes on one of those points.

theorem ConcaveOn.exists_le_of_centerMass {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} {ι : Type u_5} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} {t : Finset ι} {w : ι → 𝕜} {p : ι → E} (h : ConcaveOn 𝕜 s f) (hw₀ : ∀ i ∈ t, 0 ≤ w i) (hw₁ : 0 < Finset.sum t fun (i : ι) => w i) (hp : ∀ i ∈ t, p i ∈ s) : ∃ i ∈ t, f (p i) ≤ f (Finset.centerMass t w p)

If a function f is concave on s, then the value it takes at some center of mass of points of s is greater than the value it takes on one of those points.

theorem ConvexOn.exists_ge_of_mem_convexHull {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} (hf : ConvexOn 𝕜 ((convexHull 𝕜) s) f) {x : E} (hx : x ∈ (convexHull 𝕜) s) : ∃ y ∈ s, f x ≤ f y

Maximum principle for convex functions. If a function f is convex on the convex hull of s, then the eventual maximum of f on convexHull 𝕜 s lies in s.

theorem ConcaveOn.exists_le_of_mem_convexHull {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {s : Set E} {f : E → β} (hf : ConcaveOn 𝕜 ((convexHull 𝕜) s) f) {x : E} (hx : x ∈ (convexHull 𝕜) s) : ∃ y ∈ s, f y ≤ f x

Minimum principle for concave functions. If a function f is concave on the convex hull of s, then the eventual minimum of f on convexHull 𝕜 s lies in s.

theorem ConvexOn.le_max_of_mem_segment {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : E → β} {x : E} {y : E} {z : E} (hf : ConvexOn 𝕜 (segment 𝕜 x y) f) (hz : z ∈ segment 𝕜 x y) : f z ≤ max (f x) (f y)

Maximum principle for convex functions on a segment. If a function f is convex on the segment [x, y], then the eventual maximum of f on [x, y] is at x or y.

theorem ConcaveOn.min_le_of_mem_segment {𝕜 : Type u_1} {E : Type u_2} {β : Type u_4} [LinearOrderedField 𝕜] [AddCommGroup E] [LinearOrderedAddCommGroup β] [Module 𝕜 E] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : E → β} {x : E} {y : E} {z : E} (hf : ConcaveOn 𝕜 (segment 𝕜 x y) f) (hz : z ∈ segment 𝕜 x y) : min (f x) (f y) ≤ f z

Minimum principle for concave functions on a segment. If a function f is concave on the segment [x, y], then the eventual minimum of f on [x, y] is at x or y.

theorem ConvexOn.le_max_of_mem_Icc {𝕜 : Type u_1} {β : Type u_4} [LinearOrderedField 𝕜] [LinearOrderedAddCommGroup β] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : 𝕜 → β} {x : 𝕜} {y : 𝕜} {z : 𝕜} (hf : ConvexOn 𝕜 (Set.Icc x y) f) (hz : z ∈ Set.Icc x y) : f z ≤ max (f x) (f y)

Maximum principle for convex functions on an interval. If a function f is convex on the interval [x, y], then the eventual maximum of f on [x, y] is at x or y.

theorem ConcaveOn.min_le_of_mem_Icc {𝕜 : Type u_1} {β : Type u_4} [LinearOrderedField 𝕜] [LinearOrderedAddCommGroup β] [Module 𝕜 β] [OrderedSMul 𝕜 β] {f : 𝕜 → β} {x : 𝕜} {y : 𝕜} {z : 𝕜} (hf : ConcaveOn 𝕜 (Set.Icc x y) f) (hz : z ∈ Set.Icc x y) : min (f x) (f y) ≤ f z

Minimum principle for concave functions on an interval. If a function f is concave on the interval [x, y], then the eventual minimum of f on [x, y] is at x or y.