Stanford AA222 I Engineering Design Optimization | Spring 2025 | Multiobjective Optimization

Key Concepts

• Multi-objective Optimization: Optimizing multiple objectives simultaneously.
• Pareto Optimality: A state where no objective can be improved without worsening another.
• Pareto Frontier: The set of all Pareto optimal designs.
• Dominance: A design dominates another if it is equal or better in all objectives.
• Constraint Method: Optimizing one objective while constraining others.
• Lexicographic Method: Optimizing objectives in a prioritized order.
• Weighted Sum Method: Combining objectives into a single objective using weights.
• Goal Programming: Minimizing the distance to a goal point (e.g., utopia point).
• Weighted Exponential Sum Method: Combining goal programming with weighted objectives.
• Weighted Minmax Method: A method that can provide the complete Pareto optimal set by scanning over the weights.
• Vector Evaluated Genetic Algorithm (VEGA): Extends genetic algorithms to multi-objective settings.
• Non-domination Ranking: Ranking individuals in a population based on Pareto dominance.
• Pareto Filter: Removing dominated individuals during optimization.
• Niche Techniques: Ensuring an even spread of points along the Pareto frontier.
• Preference Elicitation: Inferring preferences (weights) through pairwise comparisons.
• Half-space: A region defined by a linear inequality.

Multi-Objective Optimization Introduction

The lecture transitions from single-objective optimization to multi-objective optimization. In single-objective optimization, the objective function outputs a single value to be optimized, while in multi-objective optimization, the objective function outputs multiple values, each representing a different objective. The goal is to optimize all these objectives simultaneously.

• Example: A PhD student might want to optimize for cool research, writing papers, happiness, advisor's happiness, and graduating in a reasonable time.

Some objectives may align (e.g., student and advisor happiness), while others may conflict (e.g., cool research vs. graduation time). This conflict leads to trade-offs.

Pareto Optimality and Dominance

The concept of Pareto optimality is introduced to deal with trade-offs. A design is Pareto optimal if improving one objective necessarily worsens another.

• Example: A point on a graph of "cool research" vs. "graduation time" is Pareto optimal if there's no point both above and to the right of it.

The Pareto frontier is the set of all Pareto optimal designs. The concept of dominance is also introduced. A design dominates another if it is equal or better in all objectives.

• Example: Julia dominates Python if it has both better readability and performance.

Mathematical Formulation

In single-objective optimization, the goal is to find the minimum point on a number line. In multi-objective optimization, the goal is to find the Pareto frontier in a multi-dimensional space of possible outputs.

Methods for Generating the Pareto Frontier

1. Exhaustive Search

One straightforward method is to generate a large number of designs, evaluate their objectives, and then identify the non-dominated designs, which approximate the Pareto frontier.

• Example: Designing many collision avoidance systems and plotting their collision rates vs. alert rates.

This method is wasteful because many designs are not on the Pareto frontier.

2. Constraint Method

The constraint method involves constraining one or more objectives and optimizing the remaining objective(s).

• Process:
  1. Constrain objective f2 to be less than or equal to a value c2.
  2. Optimize objective f1 subject to the constraint.
  3. Repeat with different values of c2 to sweep out the Pareto frontier.

3. Lexicographic Method

The lexicographic method prioritizes objectives and optimizes them in order.

• Process:
  1. Minimize objective f1, ignoring f2.
  2. Constrain f1 to be less than or equal to the minimum found in step 1.
  3. Minimize f2 subject to the constraint.
  4. Repeat with different permutations of the objective order.

This method may only find a limited number of points on the Pareto frontier (e.g., the endpoints).

4. Weighted Sum Method

The weighted sum method combines multiple objectives into a single objective by assigning weights to each objective.

• Equation: min (W1 * F1 + W2 * F2 + ... + Wn * Fn)

By varying the weights, different points on the Pareto frontier can be found. However, this method fails for non-convex Pareto frontiers.

5. Goal Programming

Goal programming minimizes the distance to a goal point (e.g., the utopia point). Different distance metrics (L1, L2, L-infinity) can be used.

• Process:
  1. Define a goal point.
  2. Minimize the LP distance to the goal point.
  3. Vary P to obtain different points on the Pareto Frontier.

6. Weighted Exponential Sum Method

The weighted exponential sum method combines goal programming with weighted objectives.

• Process:
  1. Set a goal point.
  2. Minimize a weighted exponential sum of the distances to the goal point.
  3. Vary the weights to obtain different points on the Pareto frontier.

7. Weighted Minmax Method

Taking the limit as p approaches infinity in the weighted exponential sum method yields the weighted minmax method, which can provide the complete Pareto optimal set if the weights are scanned over.

Population Methods

Standard population methods (e.g., genetic algorithms) can be adapted for multi-objective optimization.

1. Vector Evaluated Genetic Algorithm (VEGA)

VEGA extends genetic algorithms to multi-objective settings by using sub-populations, each optimized for a different objective.

2. Non-domination Ranking

Non-domination ranking ranks individuals in a population based on Pareto dominance.

• Process:
  1. Identify the non-dominated individuals (Pareto frontier).
  2. Remove these individuals and repeat the process on the remaining population.
  3. Assign ranks based on the iteration in which an individual is identified as non-dominated.

3. Pareto Filter

A Pareto filter removes dominated individuals during optimization to improve efficiency.

4. Niche Techniques

Niche techniques ensure an even spread of points along the Pareto frontier, preventing clumping.

Preference Elicitation

At some point, a single design must be chosen. Preference elicitation involves asking simpler questions to infer the decision-maker's preferences (weights) instead of directly asking for a weight vector.

• Example: Asking an expert to choose between two collision avoidance systems with different collision and alert rates.

Candy Example

A candy example demonstrates preference elicitation. A volunteer is asked to choose between different combinations of M&Ms, Sour Patch Kids, and Skittles. The responses are used to infer the volunteer's weight vector.

• Process:
  1. Ask pairwise comparison questions.
  2. Translate responses into linear inequalities (half-spaces).
  3. Update the space of possible weights based on the inequalities.
  4. Repeat until the space is sufficiently narrowed.
  5. Choose a weight vector from the remaining space.

The lecture concludes by noting that preference elicitation is an active area of research, particularly relevant to reinforcement learning from human feedback (RLHF).