Documentation

Linglib.Core.Order.Pareto

Pareto optimality and linear scalarization #

Two objectives to be minimized are compared in the product order on pairs, so the Pareto optimal points among those satisfying P under the objectives f are those with MinimalFor P f. The linear scalarization c.1 + β * c.2 is strictly monotone for β > 0, so its minimizers are Pareto optimal (MinimalFor.of_fst_add_mul_snd_le). The converse fails without convexity: a Pareto optimal point need not minimize the scalarization at any weight. As the weight β grows, the minimizers trade the second objective for the first.

Main statements #

References #

theorem strictMono_fst_add_mul_snd {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {β : 𝕜} (hβ : 0 < β) :
StrictMono fun (c : 𝕜 × 𝕜) => c.1 + β * c.2
theorem MinimalFor.of_fst_add_mul_snd_le {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {β : 𝕜} {ι : Type u_2} {P : ι → Prop} {f : ι → 𝕜 × 𝕜} {i : ι} (hβ : 0 < β) (hi : P i) (h : ∀ (j : ι), P j → (f i).1 + β * (f i).2 ≤ (f j).1 + β * (f j).2) :
MinimalFor P f i

A minimizer of the scalarization at a positive weight is Pareto optimal.

theorem exists_minimal_forall_exists_fst_add_mul_snd_lt {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] :
∃ (P : 𝕜 × 𝕜 → Prop) (c : 𝕜 × 𝕜), Minimal P c ∧ ∀ (β : 𝕜), ∃ (d : 𝕜 × 𝕜), P d ∧ d.1 + β * d.2 < c.1 + β * c.2

The converse fails without convexity. Of the points (0, 4), (4, 0) and (2, 3) the last is Pareto optimal, yet at every weight one of the others has a smaller scalarization.

theorem snd_le_of_fst_add_mul_snd_le {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {β₁ β₂ : 𝕜} {a b : 𝕜 × 𝕜} (hβ : β₁ < β₂) (h₁ : a.1 + β₁ * a.2 ≤ b.1 + β₁ * b.2) (h₂ : b.1 + β₂ * b.2 ≤ a.1 + β₂ * a.2) :
b.2 ≤ a.2
theorem fst_le_of_fst_add_mul_snd_le {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {β₁ β₂ : 𝕜} {a b : 𝕜 × 𝕜} (hβ₁ : 0 ≤ β₁) (hβ : β₁ < β₂) (h₁ : a.1 + β₁ * a.2 ≤ b.1 + β₁ * b.2) (h₂ : b.1 + β₂ * b.2 ≤ a.1 + β₂ * a.2) :
a.1 ≤ b.1
theorem antitone_snd_of_fst_add_mul_snd_le {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {c : 𝕜 → 𝕜 × 𝕜} (h : ∀ (β β' : 𝕜), (c β).1 + β * (c β).2 ≤ (c β').1 + β * (c β').2) :
Antitone fun (β : 𝕜) => (c β).2
theorem monotoneOn_fst_of_fst_add_mul_snd_le {𝕜 : Type u_1} [CommRing 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {c : 𝕜 → 𝕜 × 𝕜} (h : ∀ (β β' : 𝕜), (c β).1 + β * (c β).2 ≤ (c β').1 + β * (c β').2) :
MonotoneOn (fun (β : 𝕜) => (c β).1) (Set.Ici 0)