Kochenderfer & Wheeler, Chapter 15

Multiobjective Optimization

When you can't have it all. Explore the Pareto frontier of tradeoffs between competing objectives.

Prerequisites: Chapter 10 (Constraints), Chapter 9 (Population Methods).

Chapters

Simulations

Quizzes

Chapter 0: Competing Objectives

Design an airplane: you want it light (low fuel cost) but also strong (high safety). Making it lighter makes it weaker. Making it stronger makes it heavier. You cannot optimize both simultaneously — there is a fundamental tradeoff.

The core idea: Multiobjective optimization handles problems with multiple objectives f₁(x), ..., f_m(x) that conflict. Instead of a single optimal point, the solution is a Pareto frontier — a curve (or surface) of designs where improving one objective necessarily worsens another. The designer then chooses from this frontier based on preferences.

A multiobjective problem differs from a single-objective one because:

The solution is a set of tradeoffs (Pareto frontier), not a single point There are more design variables The problem is always convex

Chapter 1: Pareto Optimality

A design x dominates design x' if it is at least as good in every objective and strictly better in at least one. A design is Pareto optimal if no other design dominates it.

The Pareto frontier is the set of all Pareto optimal designs plotted in criterion space (the space of objective values y = f(x)). The utopia point is the (usually infeasible) point that minimizes each objective independently.

Key insight: Every point on the Pareto frontier represents a fundamentally different tradeoff. Moving along the frontier, you gain in one objective and lose in another. No point on the frontier can be improved without making another objective worse — that is the definition of optimality under competition.

A Pareto optimal design is one where:

No other design improves one objective without worsening another All objectives are at their individual minimum It has the smallest sum of objective values

Chapter 2: Constraint Methods

The ε-constraint method optimizes one objective while constraining the others: minimize f₁(x) subject to f_j(x) ≤ ε_j for j = 2,...,m. Varying the bounds ε traces the Pareto frontier.

The lexicographic method ranks objectives by priority and optimizes them sequentially. First minimize f₁, then minimize f₂ subject to f₁ ≤ f₁*, and so on.

Think of it this way: The ε-constraint method treats all-but-one objectives as "budgets." How well can you do on the primary objective given fixed budgets for the rest? Varying the budgets reveals the full tradeoff surface.

The ε-constraint method traces the Pareto frontier by:

Varying the bounds on all-but-one objectives Weighting the objectives Using a genetic algorithm

Chapter 3: Weighted Sum

The weighted sum method converts the multiobjective problem to a single objective: minimize w^>f(x), where w ≥ 0 and ∑w_i = 1. Varying w traces the Pareto frontier.

Limitation: The weighted sum method can only find points on the convex portions of the Pareto frontier. If the Pareto frontier has concave regions (bends away from the origin), some Pareto optimal points cannot be reached by any choice of weights. The contour lines of w^>f are hyperplanes that can only touch convex parts of the frontier.

The weighted sum method cannot find Pareto points in:

Nonconvex (concave) regions of the Pareto frontier The convex hull of the frontier Any region — it always works

Chapter 4: Goal Programming

Goal programming minimizes the distance from f(x) to a goal point (typically the utopia point) using an L_p norm:

minimize ||f(x) − y_goal||_p

Different norms give different tradeoff characters: L₁ tolerates one large deviation, L₂ (Euclidean) penalizes large deviations quadratically, and L_∞ minimizes the worst objective's deviation.

Think of it this way: Goal programming asks "how close can I get to having it all?" The norm controls what "close" means. L_∞ is the most egalitarian — it minimizes the maximum sacrifice in any single objective.

Goal programming with L_∞ norm minimizes:

The worst-case deviation from the goal across all objectives The sum of all deviations Only the first objective's deviation

Chapter 5: Min-Max Methods

The weighted min-max (Tchebycheff) method: minimize max_i[w_i(f_i(x) − y_i^goal)]. Unlike the weighted sum, it can find points on nonconvex portions of the Pareto frontier because the min-max contours can penetrate concavities.

To eliminate weakly Pareto optimal points, add a small augmentation term: ρ f(x)^>y_goal.

Key advantage: The weighted min-max method provides complete coverage of the Pareto frontier. Scanning over weights w produces every Pareto optimal point, including those in concave regions that the weighted sum method misses.

The weighted min-max method improves over weighted sum by:

Finding Pareto points in nonconvex regions of the frontier Being faster to compute Requiring fewer objectives

Chapter 6: Population Approaches

Population methods naturally extend to multiobjective problems because they maintain many individuals that can spread across the Pareto frontier.

The vector evaluated genetic algorithm (VEGA) divides the population into subpopulations, each selected by a different objective. Crossover and mutation then mix individuals from different subpopulations.

More advanced methods like NSGA-II use non-dominated sorting (rank individuals by Pareto dominance) and crowding distance (encourage diversity along the frontier).

Key insight: Population methods produce an approximation of the entire Pareto frontier in a single run. No need to solve many single-objective problems with different weights. The population naturally spreads to cover the frontier.

Population methods are well-suited for multiobjective optimization because:

Many individuals can spread across the entire Pareto frontier They are always faster than scalarization methods They do not require objective function evaluations

Chapter 7: Preference Elicitation

Once the Pareto frontier is known, the designer must choose a point. Preference elicitation formalizes this choice. Methods range from simple (ask for weights) to interactive (present pairwise comparisons and learn the preference model).

The challenge: people are inconsistent in expressing preferences over high-dimensional tradeoffs. Interactive methods that present specific design comparisons tend to produce more reliable preferences than asking for abstract weight vectors.

Think of it this way: Optimization produces the menu of non-dominated dishes. Preference elicitation is the waiter helping you choose. The best waiter shows you specific pairs and asks "which do you prefer?" rather than asking you to assign numerical scores.

Preference elicitation is needed because:

The Pareto frontier contains many optimal tradeoffs; a designer must choose one The optimizer cannot find any solution There is only one Pareto optimal point

Chapter 8: Summary

Method	Produces	Handles Nonconvex Frontier?
Weighted sum	Points via weight sweeping	No
ε-constraint	Points via bound sweeping	Yes
Goal programming	Single point closest to goal	Depends on norm
Weighted min-max	Complete frontier via weight sweeping	Yes
Population methods	Approximate frontier in one run	Yes

Looking ahead: Chapter 16 covers sampling plans — how to choose evaluation points when function evaluations are expensive and you need maximum information from minimum samples.

The Pareto frontier is the set of designs where:

No objective can be improved without worsening another All objectives are minimized simultaneously The weighted sum is minimized