Multi-Objective Optimization

Multi-objective optimization addresses problems of the form min/max f(x) = (f_1(x), f_2(x), ..., f_k(x)) with k≥2 objectives over a common constraint set x ∈ X. In place of a single global optimum, the Pareto-efficient set is sought: x* is Pareto-optimal iff no y ∈ X satisfies f_i(y) ≤ f_i(x*) for all i with strict inequality for at least one j (Pareto 1906). Scalarization approaches fall into five families: (1) Weighted sum — min Σ w_i f_i, recovers points on the convex hull of the Pareto frontier but misses non-convex regions; (2) ε-constraint method (Haimes et al. 1971) — optimize one objective while the others are bounded as f_i ≤ ε_i; can sweep the entire frontier; (3) Lexicographic ordering — objectives are optimized sequentially by priority, the prior optimum value entering as a constraint at the next stage; (4) Goal programming (Charnes and Cooper 1961) — aspiration level per objective, deviation variables minimized; (5) Multi-objective metaheuristics — NSGA-II (Deb et al. 2002), SPEA2 (Zitzler et al. 2001) evolve a population that converges in parallel to the Pareto front. Complexity: each scalarization is an LP if objectives are linear; enumerating or representing the full Pareto set is generally NP-hard. Canonical monographs include Miettinen (1999), Steuer (1986), and Ehrgott (2005).