Pareto optimality via scalarization
ProvedConvexOptimization.scalarization_sufficient_paretoScalarization produces Pareto optimal points.
Let and let be a vector objective with components . Fix weights with for every , and suppose minimizes the scalarized objective:
Then is Pareto optimal for : there is no with for all and — no feasible point improves some component without worsening another.
Scalarization is the standard device for reducing multicriterion optimization to the single-objective theory of this mission: choosing strictly positive weights and solving one ordinary problem yields a Pareto point, and sweeping the weights traces out a family of them. Strict positivity is essential — with a zero weight the minimizer may be dominated in the ignored coordinate.
Formalization Note The vector objective is a function into Fin k → ℝ; domination is expressed as componentwise together with as functions, and the conclusion is the negation of an existential. No convexity of or of the components is needed for this direction. Source: B&V §4.7.4, p. 178.
import Mathlib open scoped RealInnerProductSpace ENNReal open MeasureTheory
theorem ConvexOptimization.scalarization_sufficient_pareto {n k : ℕ}
(X : Set (EuclideanSpace ℝ (Fin n)))
(f : EuclideanSpace ℝ (Fin n) → Fin k → ℝ)
(lam : Fin k → ℝ) (hlam : ∀ i, 0 < lam i)
(xs : EuclideanSpace ℝ (Fin n)) (hxs : xs ∈ X)
(hmin : ∀ y ∈ X, ∑ i, lam i * f xs i ≤ ∑ i, lam i * f y i) :
¬∃ y ∈ X, (∀ i, f y i ≤ f xs i) ∧ f y ≠ f xs := by
sorry