The lecture introduces multi-objective optimization by explaining Pareto optimality and various methods to approximate the Pareto frontier, including weighted sums, goal programming, and population-based algorithms, highlighting their strengths and limitations. It also addresses the challenge of selecting a single design from the frontier through preference elicitation techniques that infer stakeholder priorities via interactive comparisons.
In this lecture on multi-objective optimization, Sydney introduces the concept by contrasting it with single-objective optimization, which the students have studied so far. Unlike single-objective problems that yield one output to optimize, multi-objective optimization involves multiple objectives that often conflict, requiring trade-offs. Sydney uses relatable examples, such as optimizing various aspects of a PhD experience or choosing programming languages based on readability and performance, to illustrate how objectives can align or conflict. The key concept introduced is Pareto optimality, where a design is Pareto optimal if improving one objective necessarily worsens another, and the Pareto frontier represents the set of all such optimal trade-offs.
The lecture then explores mathematical formulations of multi-objective optimization problems, emphasizing that instead of seeking a single minimum point, the goal is to identify the entire Pareto frontier. Sydney discusses straightforward methods like sampling many designs and selecting non-dominated points to approximate the frontier but notes this approach is inefficient. More systematic methods are introduced, including the constraint method, which fixes one objective within a bound and optimizes the other, and the lexicographic method, which optimizes objectives sequentially with constraints. However, these methods often yield only limited points on the frontier.
To generate more comprehensive Pareto frontiers, Sydney explains the weighted sum method, where objectives are combined into a single weighted sum and optimized. This method can produce a range of Pareto optimal points by varying weights but fails on non-convex frontiers, missing some optimal solutions. To address this, goal programming is introduced, which minimizes the distance to a chosen goal point (often the utopia point) using different norms, allowing access to non-convex regions. The weighted exponential sum method further generalizes this by combining weighting and distance metrics, improving coverage of the Pareto frontier, though it still may not guarantee completeness without certain limits.
Population-based optimization methods, such as vector evaluated genetic algorithms, are also adapted for multi-objective problems. These methods maintain subpopulations optimized for different objectives and use non-domination ranking to evaluate and select individuals based on Pareto dominance layers. Additional techniques like Pareto filtering and niche methods help maintain diversity and focus on promising solutions. These approaches enable efficient exploration of the Pareto frontier in complex problems where traditional methods may struggle.
Finally, Sydney discusses the practical challenge of selecting a single design from the Pareto frontier, introducing preference elicitation as a way to infer stakeholder weights through pairwise comparisons rather than direct questioning. Using a candy preference example, the lecture demonstrates how linear inequalities derived from choices constrain the possible weight vectors, narrowing down preferences. This interactive approach can be refined by adaptive querying and probabilistic modeling to handle imperfect human responses. The lecture concludes by highlighting that multi-objective optimization is not only about finding the frontier but also about understanding and incorporating preferences to make informed design decisions.