| name | multi-objective-optimization |
| description | Multi-objective optimization — Pareto front, dominance, NSGA-II, MOEA/D, weighted sum method, epsilon-constraint, scalarization, design space exploration, surrogate models (kriging, response surface), hypervolume indicator, design of experiments (LHS, Sobol), MATLAB gamultiobj, engineering trade-off analysis. |
| metadata | {"priority":7,"promptSignals":{"phrases":["multi-objective optimization","Pareto front","NSGA-II","Pareto optimal","multi-objective design","trade-off optimization"],"minScore":3}} |
Multi-Objective Optimization — Complete Skill
Fundamentals
Multi-Objective Problem Formulation
General form:
min F(x) = [f₁(x), f₂(x), ..., f_k(x)]ᵀ [k objective functions; x = design variables]
subject to: g_i(x) ≤ 0 [inequality constraints]
h_j(x) = 0 [equality constraints]
x_lb ≤ x ≤ x_ub [variable bounds]
Key challenge: objectives typically conflict → no single solution minimizes all objectives simultaneously
Pareto Dominance and Pareto Front
Pareto dominance:
Solution x₁ dominates x₂ (written x₁ ≻ x₂) if:
- x₁ is no worse than x₂ in ALL objectives: f_i(x₁) ≤ f_i(x₂) for all i
- x₁ is strictly better in AT LEAST ONE objective: f_j(x₁) < f_j(x₂) for some j
Pareto front: set of non-dominated solutions; each Pareto solution is optimal in the sense that no objective can be improved without worsening another
Pareto set (design space): corresponding design variables for Pareto front solutions
Pareto front (objective space): image of Pareto set in objective function space
Hypervolume indicator: measure of Pareto front quality
HV(P, r) = vol(∪_{p∈P} [p, r]) [volume dominated by Pareto front P relative to reference point r]
Larger HV → better Pareto front (closer to ideal and more diverse)
Scalarization Methods
Weighted Sum Method
Convert to single objective:
f_scalar = Σ w_i × f_i(x) [w_i ≥ 0; Σ w_i = 1; user-specified weights]
Solve single-objective optimization for each weight vector → one Pareto point per solve
Limitation:
Cannot find all Pareto solutions if Pareto front is non-convex (some solutions missed)
Weight selection not intuitive; requires multiple runs (N_weight_vectors solve calls)
Use when: objectives commensurate in units; convex Pareto front expected
Example: mass minimization + cost minimization of structural design
w₁ = 0.7 (more weight to cost); w₂ = 0.3; f = 0.7 × (mass/mass_max) + 0.3 × (cost/cost_max)
Vary w₁ from 0 to 1 in 11 steps → 11 Pareto points
ε-Constraint Method
Convert all but one objective to constraints:
min f₁(x) [primary objective]
subject to: f_i(x) ≤ ε_i [i = 2, ..., k; bound all other objectives]
Advantages:
- Finds all Pareto solutions (even non-convex fronts)
- Intuitive: ε_i = acceptable limit for secondary objectives
- Systematic: vary ε_i over ranges → trace full Pareto front
Computational cost: N_ε_levels^(k-1) optimizations for k objectives; grows quickly
Lexicographic Method
Objective priority ranking:
- Minimize f₁ (most important)
- Minimize f₂ subject to f₁ ≤ f₁* + ε₁
- Continue in priority order
Use when: clear preference ordering among objectives; quick decision without Pareto front
Evolutionary Multi-Objective Algorithms
NSGA-II (Non-Dominated Sorting Genetic Algorithm II — Deb et al., 2002)
Most widely used MOEA; MATLAB gamultiobj is NSGA-II based
Algorithm:
- Initialize population P (N individuals)
- Create offspring Q via crossover + mutation
- Combine P ∪ Q (size 2N)
- Rank by non-domination: Front 1 (Pareto), Front 2, ...
- Select top N individuals: fill by fronts; crowding distance to break ties within front
- Repeat until termination
Crowding distance: measure of local density in objective space; prefer sparse regions → diversity preserved
d_i = Σ_m (f_m(x_i+1) - f_m(x_i-1)) / (f_m^max - f_m^min) [sum over all objectives; larger = more isolated]
Parameters:
Population size N: 50–200 (larger → better coverage, more evaluations)
Generations: 100–500 (sufficient for convergence; monitor hypervolume)
Crossover probability: 0.9; mutation probability: 1/n_variables
Computational cost: N × generations × evaluation_time; typical 5,000–100,000 function evaluations
NSGA-III (Reference Point Based)
For k > 3 objectives (many-objective):
Crowding distance fails in high dimensions → reference points maintain diversity
Reference points on hyperplane: uniform grid of W = C(k-1+H, H) points (H = division parameter)
Assignment: solutions assigned to closest reference point → diversity along reference lines
Use when: k > 3 objectives; complex trade-off structure
MOEA/D (Multi-Objective Evolutionary Algorithm with Decomposition)
Decomposes multi-objective into N single-objective subproblems using weight vectors:
Each subproblem: minimize Tchebycheff scalar: max_i w_i × |f_i - z_i*| [z* = ideal point]
Neighbors (nearby weight vectors) cooperate in solving adjacent subproblems
Advantage: efficient; good for large populations; fewer evaluations than NSGA-II for same quality
MOPSO (Multi-Objective Particle Swarm Optimization)
Each particle has a velocity and position:
v_{i+1} = w × v_i + c₁ × rand × (p_best - x) + c₂ × rand × (g_best - x)
Multiple global bests from Pareto archive → selection from archive for diverse exploration
Good for: continuous variables; fast convergence; low dimensionality (< 20 variables)
Surrogate-Based Multi-Objective Optimization
Problem
Expensive evaluations: each function evaluation = FEA simulation (minutes–hours) → NSGA-II with 10,000 evaluations = infeasible
Solution: build surrogate (metamodel) from initial DoE → optimize surrogate → cheaply find Pareto front → validate with true model
Design of Experiments (DoE)
Latin Hypercube Sampling (LHS):
N_samples stratified samples; each dimension divided into N equal intervals; one sample per interval
Better space-filling than random; N_samples = 10 × n_variables (minimum); 50–100 for good coverage
Sobol sequence: quasi-random; better uniformity than LHS; preferred for high dimensions
Full factorial: 2^k × 3 levels (too expensive for k > 5 variables)
D-optimal design: maximize determinant of information matrix; minimizes estimation uncertainty
Kriging (Gaussian Process Regression)
Interpolation with uncertainty estimate:
ŷ(x) = μ(x) + Z(x) [Z = realization of Gaussian process with covariance k(x, x')]
Gaussian covariance function:
k(x, x') = σ² × exp(-0.5 × Σ (x_i - x'_i)² / l_i²) [l_i = length scale per dimension]
Prediction:
ŷ(x*) = μ + K_^T K⁻¹ (y - μ_1) [posterior mean; deterministic interpolation at training points]
Var(ŷ(x)) = σ² - K_^T K⁻¹ K_ [posterior variance; useful for exploration (uncertainty sampling)]
Hyperparameters (σ, l_i): learned by maximum likelihood on training data
EGO (Efficient Global Optimization): infill criterion using EI (Expected Improvement) to add points where improvement expected
EI(x) = E[max(y_best - ŷ(x), 0)] = (y_best - ŷ) × Φ(z) + σ × φ(z) [Φ = CDF; φ = PDF; z = (y_best - ŷ)/σ]
Multi-objective EGO:
ParEGO (Knowles 2006): random weight vector each iteration → weighted sum → single-objective EGO → builds Pareto front incrementally
TSEMO (Thompson Sampling for Efficient Multi-objective Optimization): probabilistic; efficient
Response Surface Method (RSM)
Polynomial approximation:
ŷ(x) = β₀ + Σ β_i x_i + Σ β_ii x_i² + Σ β_ij x_i x_j [second-order polynomial]
Fit by least squares; requires N ≥ (n+1)(n+2)/2 samples (n = variables)
Validation:
R² > 0.95: good fit; R²_adjusted corrected for number of terms
RMSE: root mean square cross-validation error; use k-fold cross-validation
Limitation vs. Kriging: RSM is global approximation (smoother; may miss local detail); Kriging is exact interpolation
Engineering Trade-off Analysis
Pareto Front Visualization
2 objectives: scatter plot f₁ vs. f₂ → continuous Pareto front visible; select "knee point" (maximum curvature)
3 objectives: 3D scatter; parallel coordinate plots; color-coded
k > 3 objectives: parallel coordinates → one axis per objective; lines connect objective values per solution; filter regions of interest
Knee Point Selection
Knee point: Pareto solution with best trade-off; maximum normalized distance from utopia-nadir line
k_i = ||(F(x_i) - F_utopia) × n_hat|| [n_hat = unit normal to utopia-nadir line]
Knee = max(k_i)
Alternatively: allow decision maker to select weight vector reflecting preferences → weighted Chebyshev scalarization guides to appropriate Pareto region
Robust Optimization
Problem: design may be Pareto optimal for nominal conditions but sensitive to uncertainty
Robust Pareto front: optimize E[F(x, δ)] and Var[F(x, δ)] simultaneously [δ = uncertain parameters]
Solution: Pareto front of (mean performance vs. variance) → decision maker selects preferred robustness level
MATLAB gamultiobj
% Define multi-objective function
f = @(x) [objective1(x), objective2(x)];
% Variable bounds
lb = [0 0 0]; ub = [10 5 8];
% Options
options = optimoptions('gamultiobj', ...
'PopulationSize', 100, ...
'MaxGenerations', 200, ...
'PlotFcn', 'gaplotpareto', ...
'Display', 'iter');
% Inequality constraints (optional)
A = []; b = [];
Aeq = []; beq = [];
nonlcon = @myconstraint;
% Run NSGA-II
[x_pareto, f_pareto, exitflag, output] = gamultiobj(f, 3, A, b, Aeq, beq, lb, ub, nonlcon, options);
% Plot Pareto front
scatter(f_pareto(:,1), f_pareto(:,2), 'filled');
xlabel('Objective 1'); ylabel('Objective 2');
title('Pareto Front');
Standards and References
| Source | Scope |
|---|
| Deb et al. (2002) IEEE Trans. Evol. Comp. | NSGA-II original paper |
| Deb (2001) Multi-Objective Optimization Using Evolutionary Algorithms | Standard textbook |
| Jones et al. (1998) J. Global Optim. | EGO (kriging + EI) |
| Knowles (2006) IEEE Trans. Evol. Comp. | ParEGO (MOEGO) |
| ISO/IEC 14882 | C++ standard (for custom implementation) |
Output
Provide: problem formulation (objectives f₁, f₂, ... [units]; constraints g_i; design variables x with bounds), algorithm selected (NSGA-II/MOEA/D/surrogate-based) with justification (evaluation cost per function call [s]), DoE plan (N_samples, LHS/Sobol), surrogate type (Kriging/RSM) and validation R²/RMSE, population size and generations (if MOEA), Pareto front description (N_Pareto points; range of f₁ and f₂), knee point identified (design variable values and objective values), sensitivity analysis (which variable dominates f₁? f₂?), robust assessment (variance of knee point performance under ±10% parameter uncertainty), MATLAB code snippet, and applicable reference (Deb 2001, NSGA-II 2002).
