Quasiconvex and quasiconcave functions

This file defines quasiconvexity, quasiconcavity and quasilinearity of functions, which are generalizations of unimodality and monotonicity. Convexity implies quasiconvexity, concavity implies quasiconcavity, and monotonicity implies quasilinearity.

Main declarations

• QuasiconvexOn 𝕜 s f: Quasiconvexity of the function f on the set s with scalars 𝕜. This means that, for all r, {x ∈ s | f x ≤ r} is 𝕜-convex.
• QuasiconcaveOn 𝕜 s f: Quasiconcavity of the function f on the set s with scalars 𝕜. This means that, for all r, {x ∈ s | r ≤ f x} is 𝕜-convex.
• QuasilinearOn 𝕜 s f: Quasilinearity of the function f on the set s with scalars 𝕜. This means that f is both quasiconvex and quasiconcave.

References

• https://en.wikipedia.org/wiki/Quasiconvex_function

def QuasiconvexOn (𝕜 : Type u_1) {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] (s : Set E) (f : E → β) : Prop

A function is quasiconvex if all its sublevels are convex. This means that, for all r, {x ∈ s | f x ≤ r} is 𝕜-convex.

Equations

• QuasiconvexOn 𝕜 s f = ∀ (r : β), Convex 𝕜 {x : E | x ∈ s ∧ f x ≤ r}

def QuasiconcaveOn (𝕜 : Type u_1) {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] (s : Set E) (f : E → β) : Prop

A function is quasiconcave if all its superlevels are convex. This means that, for all r, {x ∈ s | r ≤ f x} is 𝕜-convex.

Equations

• QuasiconcaveOn 𝕜 s f = ∀ (r : β), Convex 𝕜 {x : E | x ∈ s ∧ r ≤ f x}

def QuasilinearOn (𝕜 : Type u_1) {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] (s : Set E) (f : E → β) : Prop

A function is quasilinear if it is both quasiconvex and quasiconcave. This means that, for all r, the sets {x ∈ s | f x ≤ r} and {x ∈ s | r ≤ f x} are 𝕜-convex.

Equations

• QuasilinearOn 𝕜 s f = (QuasiconvexOn 𝕜 s f ∧ QuasiconcaveOn 𝕜 s f)

theorem QuasiconvexOn.dual {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasiconvexOn 𝕜 s f → QuasiconcaveOn 𝕜 s (⇑OrderDual.toDual ∘ f)

theorem QuasiconcaveOn.dual {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasiconcaveOn 𝕜 s f → QuasiconvexOn 𝕜 s (⇑OrderDual.toDual ∘ f)

theorem QuasilinearOn.dual {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasilinearOn 𝕜 s f → QuasilinearOn 𝕜 s (⇑OrderDual.toDual ∘ f)

theorem Convex.quasiconvexOn_of_convex_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} (hs : Convex 𝕜 s) (h : ∀ (r : β), Convex 𝕜 {x : E | f x ≤ r}) : QuasiconvexOn 𝕜 s f

theorem Convex.quasiconcaveOn_of_convex_ge {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} (hs : Convex 𝕜 s) (h : ∀ (r : β), Convex 𝕜 {x : E | r ≤ f x}) : QuasiconcaveOn 𝕜 s f

theorem QuasiconvexOn.convex {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} [IsDirectedOrder β] (hf : QuasiconvexOn 𝕜 s f) : Convex 𝕜 s

theorem QuasiconcaveOn.convex {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LE β] [SMul 𝕜 E] {s : Set E} {f : E → β} [IsCodirectedOrder β] (hf : QuasiconcaveOn 𝕜 s f) : Convex 𝕜 s

theorem QuasiconvexOn.monotone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Monotone g) (hf : QuasiconvexOn 𝕜 s f) : QuasiconvexOn 𝕜 s (g ∘ f)

theorem QuasiconvexOn.antitone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Antitone g) (hf : QuasiconvexOn 𝕜 s f) : QuasiconcaveOn 𝕜 s (g ∘ f)

theorem QuasiconcaveOn.monotone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Monotone g) (hf : QuasiconcaveOn 𝕜 s f) : QuasiconcaveOn 𝕜 s (g ∘ f)

theorem QuasiconcaveOn.antitone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Antitone g) (hf : QuasiconcaveOn 𝕜 s f) : QuasiconvexOn 𝕜 s (g ∘ f)

theorem QuasilinearOn.monotone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Monotone g) (hf : QuasilinearOn 𝕜 s f) : QuasilinearOn 𝕜 s (g ∘ f)

theorem QuasilinearOn.antitone_comp {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} {γ : Type u_7} [LinearOrder β] [Preorder γ] {s : Set E} {f : E → β} {g : β → γ} (hg : Antitone g) (hf : QuasilinearOn 𝕜 s f) : QuasilinearOn 𝕜 s (g ∘ f)

theorem Convex.quasiconvexOn_restrict {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} [Preorder β] {s : Set E} {f : E → β} {t : Set E} (hf : QuasiconvexOn 𝕜 s f) (hst : t ⊆ s) (ht : Convex 𝕜 t) : QuasiconvexOn 𝕜 t f

theorem Convex.quasiconcaveOn_restrict {𝕜 : Type u_4} {E : Type u_5} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {β : Type u_6} [Preorder β] {s : Set E} {f : E → β} {t : Set E} (hf : QuasiconcaveOn 𝕜 s f) (hst : t ⊆ s) (ht : Convex 𝕜 t) : QuasiconcaveOn 𝕜 t f

theorem QuasiconcaveOn.isPreconnected_preimage_subtype {E : Type u_4} [AddCommGroup E] [Module ℝ E] [TopologicalSpace E] [IsTopologicalAddGroup E] [ContinuousSMul ℝ E] {β : Type u_5} [Preorder β] {f : E → β} {s : Set E} {t : β} (hfc : QuasiconcaveOn ℝ s f) : IsPreconnected (Subtype.val ⁻¹' f ⁻¹' Set.Ici t)

If f is quasiconcave, then its over-levels are connected.

theorem QuasiconvexOn.isPreconnected_preimage_subtype {E : Type u_4} [AddCommGroup E] [Module ℝ E] [TopologicalSpace E] [IsTopologicalAddGroup E] [ContinuousSMul ℝ E] {β : Type u_5} [Preorder β] {f : E → β} {s : Set E} {t : β} (hfc : QuasiconvexOn ℝ s f) : IsPreconnected (Subtype.val ⁻¹' f ⁻¹' Set.Iic t)

If f is quasiconcave, then its under-levels are connected.

theorem QuasilinearOn.isPreconnected_preimage_subtype {E : Type u_4} [AddCommGroup E] [Module ℝ E] [TopologicalSpace E] [IsTopologicalAddGroup E] [ContinuousSMul ℝ E] {β : Type u_5} [Preorder β] {f : E → β} {s : Set E} {t : β} (hfc : QuasilinearOn ℝ s f) : IsPreconnected (Subtype.val ⁻¹' f ⁻¹' Set.Iic t)

theorem QuasiconvexOn.sup {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {s : Set E} {f g : E → β} [SemilatticeSup β] (hf : QuasiconvexOn 𝕜 s f) (hg : QuasiconvexOn 𝕜 s g) : QuasiconvexOn 𝕜 s (f ⊔ g)

theorem QuasiconcaveOn.inf {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] {s : Set E} {f g : E → β} [SemilatticeInf β] (hf : QuasiconcaveOn 𝕜 s f) (hg : QuasiconcaveOn 𝕜 s g) : QuasiconcaveOn 𝕜 s (f ⊓ g)

theorem quasiconvexOn_iff_le_max {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasiconvexOn 𝕜 s f ↔ Convex 𝕜 s ∧ ∀ ⦃x : E⦄, x ∈ s → ∀ ⦃y : E⦄, y ∈ s → ∀ ⦃a b : 𝕜⦄, 0 ≤ a → 0 ≤ b → a + b = 1 → f (a • x + b • y) ≤ max (f x) (f y)

theorem quasiconcaveOn_iff_min_le {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasiconcaveOn 𝕜 s f ↔ Convex 𝕜 s ∧ ∀ ⦃x : E⦄, x ∈ s → ∀ ⦃y : E⦄, y ∈ s → ∀ ⦃a b : 𝕜⦄, 0 ≤ a → 0 ≤ b → a + b = 1 → min (f x) (f y) ≤ f (a • x + b • y)

theorem quasilinearOn_iff_mem_uIcc {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder β] [SMul 𝕜 E] {s : Set E} {f : E → β} : QuasilinearOn 𝕜 s f ↔ Convex 𝕜 s ∧ ∀ ⦃x : E⦄, x ∈ s → ∀ ⦃y : E⦄, y ∈ s → ∀ ⦃a b : 𝕜⦄, 0 ≤ a → 0 ≤ b → a + b = 1 → f (a • x + b • y) ∈ Set.uIcc (f x) (f y)

theorem QuasiconvexOn.convex_lt {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder β] [SMul 𝕜 E] {s : Set E} {f : E → β} (hf : QuasiconvexOn 𝕜 s f) (r : β) : Convex 𝕜 {x : E | x ∈ s ∧ f x < r}

theorem QuasiconcaveOn.convex_gt {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder β] [SMul 𝕜 E] {s : Set E} {f : E → β} (hf : QuasiconcaveOn 𝕜 s f) (r : β) : Convex 𝕜 {x : E | x ∈ s ∧ r < f x}

theorem ConvexOn.quasiconvexOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [AddCommMonoid β] [PartialOrder β] [IsOrderedAddMonoid β] [Module 𝕜 E] [Module 𝕜 β] [PosSMulMono 𝕜 β] {s : Set E} {f : E → β} (hf : ConvexOn 𝕜 s f) : QuasiconvexOn 𝕜 s f

theorem ConcaveOn.quasiconcaveOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [AddCommMonoid β] [PartialOrder β] [IsOrderedAddMonoid β] [Module 𝕜 E] [Module 𝕜 β] [PosSMulMono 𝕜 β] {s : Set E} {f : E → β} (hf : ConcaveOn 𝕜 s f) : QuasiconcaveOn 𝕜 s f

theorem MonotoneOn.quasiconvexOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : MonotoneOn f s) (hs : Convex 𝕜 s) : QuasiconvexOn 𝕜 s f

theorem MonotoneOn.quasiconcaveOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : MonotoneOn f s) (hs : Convex 𝕜 s) : QuasiconcaveOn 𝕜 s f

theorem MonotoneOn.quasilinearOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : MonotoneOn f s) (hs : Convex 𝕜 s) : QuasilinearOn 𝕜 s f

theorem AntitoneOn.quasiconvexOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : AntitoneOn f s) (hs : Convex 𝕜 s) : QuasiconvexOn 𝕜 s f

theorem AntitoneOn.quasiconcaveOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : AntitoneOn f s) (hs : Convex 𝕜 s) : QuasiconcaveOn 𝕜 s f

theorem AntitoneOn.quasilinearOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {s : Set E} {f : E → β} (hf : AntitoneOn f s) (hs : Convex 𝕜 s) : QuasilinearOn 𝕜 s f

theorem Monotone.quasiconvexOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Monotone f) : QuasiconvexOn 𝕜 Set.univ f

theorem Monotone.quasiconcaveOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Monotone f) : QuasiconcaveOn 𝕜 Set.univ f

theorem Monotone.quasilinearOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Monotone f) : QuasilinearOn 𝕜 Set.univ f

theorem Antitone.quasiconvexOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Antitone f) : QuasiconvexOn 𝕜 Set.univ f

theorem Antitone.quasiconcaveOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Antitone f) : QuasiconcaveOn 𝕜 Set.univ f

theorem Antitone.quasilinearOn {𝕜 : Type u_1} {E : Type u_2} {β : Type u_3} [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [PartialOrder β] [Module 𝕜 E] [PosSMulMono 𝕜 E] {f : E → β} (hf : Antitone f) : QuasilinearOn 𝕜 Set.univ f

theorem QuasilinearOn.monotoneOn_or_antitoneOn {𝕜 : Type u_1} {β : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {s : Set 𝕜} {f : 𝕜 → β} [LinearOrder β] (hf : QuasilinearOn 𝕜 s f) : MonotoneOn f s ∨ AntitoneOn f s

theorem quasilinearOn_iff_monotoneOn_or_antitoneOn {𝕜 : Type u_1} {β : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {s : Set 𝕜} {f : 𝕜 → β} [LinearOrder β] (hs : Convex 𝕜 s) : QuasilinearOn 𝕜 s f ↔ MonotoneOn f s ∨ AntitoneOn f s