PaperlayerView exact revision on arXiv

Source-linked AI summary

Multicriteria Optimization and Decision Making: Principles, Algorithms and Case Studies

Michael Emmerich, André Deutz

arXiv:2407.00359v6math.OCmath.NA

TL;DR

Real-world optimization and decision problems involve constraints and conflicting criteria, so ideal solutions are uncommon and good compromises are needed. This reader introduces multicriteria optimization and decision making through mathematical modeling, foundational analysis, and representative solution methods, progressing from linear programming to nonlinear optimality conditions and set-oriented algorithms. Its central scope is an accessible, broad treatment of the field, while the methods discussed expose limitations such as the difficulty of computing the Nadir point and the instance-dependent nature of NP-complete problem difficulty.

  • Problem

    Real-world optimization and decision problems involve constraints and conflicting criteria, making ideal solutions uncommon and motivating the search for good compromises.

  • Method

    The reader develops an accessible, broad introduction centered on mathematical modeling and foundations, progressing from linear programming and single-point methods to nonlinear optimality conditions and set-oriented algorithms.

  • Results

    The reader presents multicriteria optimization and decision making as a broad field covering Pareto optimization, utility modeling, optimality analysis, and representative methods for obtaining Pareto-front approximations.

  • Takeaways & Limitations

    The material supports systematic analysis of conflicting objectives through Pareto solutions, human-interpretable utility functions, and single-point methods used as building blocks for Pareto-front computation.

  • Takeaways & Limitations

    Pareto-front approximation through compromise programming requires knowledge of the ideal and Nadir points, whose computation can itself be difficult.

Abstract

from arXiv · show

Real-world decision and optimization problems, often involve constraints and conflicting criteria. For example, choosing a travel method must balance speed, cost, environmental footprint, and convenience. Similarly, designing an industrial process must consider safety, environmental impact, and cost efficiency. Ideal solutions where all objectives are optimally met are rare; instead, we seek good compromises and aim to avoid lose-lose scenarios. Multicriteria optimization offers computational techniques to compute Pareto optimal solutions, aiding decision analysis and decision making. This reader offers an introduction to this topic and has been developed on the basis of the revised edition of the reader for the MSc computer science course "Multicriteria Optimization and Decision Analysis" at the Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands. This course was taught annually by the first author from 2007 to 2023 as a single semester course with lectures and practicals. Our aim was to make the material accessible to MSc students who do not study mathematics as their core discipline by introducing basic numerical analysis concepts when necessary and providing numerical examples for interesting cases. The introduction is organized in a unique didactic manner developed by the authors, starting from more simple concepts such as linear programming and single-point methods, and advancing from these to more difficult concepts such as optimality conditions for nonlinear optimization and set-oriented solution algorithms. Besides, we focus on the mathematical modeling and foundations rather than on specific algorithms, though not excluding the discussion of some representative examples of solution algorithms.

Revised Version

The revised reader adds practical modeling guidance, clarifies foundational theory, expands coverage of optimization methods, and introduces new examples, references, and software resources.

  • A new section explains how to linearize mathematical programming models, especially for integer linear programming solvers.
  • The KKT chapter corrects a sign error, expands constraint-qualification coverage, and adds exercises based on course assignments and exams.
  • New material provides historical context for the NP = P problem in combinatorial optimization and introduces preference-elicitation and value-focused workflows for utility functions.
  • The reader expands evolutionary-algorithm coverage and introduces the KLP algorithm for computing non-dominated sets.
  • Additional updates include optimization software references, an analytical rectangular-region example, and historical discussion of goal programming.

Introduction

The introduction frames multicriteria optimization and decision making as a system-design and analysis field spanning formal models, human decisions, and computational methods. It presents modeling, simulation, optimization, and inverse design as connected tasks for addressing conflicting objectives and complex systems.

  • Introduction: Multicriteria optimization and decision making combines structural optimization methods with systematic evaluation of alternatives for real-world choices.
  • Introduction: Core formal questions concern stating problems, distinguishing single- from multi-objective optimization, classifying solutions, and identifying optimality conditions.
  • Introduction: The field also asks how efficient algorithms can obtain optimal solutions or approximations and how solution sets are geometrically structured.
  • Introduction: Decision analysis considers goals, cognition, group decisions, alternatives, criterion measurements, uncertainties, objectives, constraints, and domain-specific procedures.
  • Introduction: The lecture notes mainly emphasize structural aspects while also addressing human-centric decision making and the selection, adaptation, and evaluation of MOO tools.
  • System design and analysis: System analysis studies modeling, simulation, and synthesis of complex systems, using simulation models to represent internal structures and input-output relationships.
  • System design and analysis: Simulation predicts output states for input vectors, while optimization selects inputs to maximize or minimize outputs and inverse design minimizes deviation from desired outputs.
  • System design and analysis: Multi-objective optimization extends single-objective optimization to multiple outputs, using scalarization or Pareto techniques to obtain solutions of interest.

Time Complexity of Solving Linear Programs

Linear programming has different complexity guarantees depending on the solution method: simplex is practical but can be exponential in the worst case, while interior-point and ellipsoid methods are polynomial. LP geometry, convex feasible regions, and optimized solvers support these methods and their applications.

  • Simplex is widely used in practice, but its worst-case time complexity is O(2n) for pathological cases.
  • Interior-point methods solve LPs in polynomial time, specifically in O(n3.5L), where L is the input size.
  • The ellipsoid method also has polynomial-time complexity but is generally outperformed by interior-point methods in practice.
  • For large-scale LPs, CPLEX, Gurobi, CBC, and LPSOLVE combine optimized simplex and interior-point implementations.
  • LP feasible regions are convex, and under linear independence assumptions the optimizer is unique and lies at a boundary vertex defined by active constraints.
  • MILP and ILP problems are NP-hard, so currently known exact algorithms can require computational effort growing at least exponentially with input size n.

1.4 Pareto dominance

Pareto dominance compares solutions across multiple criteria when no single solution is best in every objective. The resulting non-dominated set is the Pareto front, which supports subsequent trade-off-based decision making.

  • The Pareto front is the set of all non-dominated solutions and is always mutually incomparable.
  • A solution Pareto dominates another when it is better in at least one criterion and no worse in any other criterion.
  • A solution is Pareto optimal when no other solution dominates it, so improving one criterion requires worsening another.
  • Pareto optimization seeks the non-dominated set YN for Y = f(X), the image of the decision space under the objective map.
  • Adding an objective preserves mutual non-dominance between existing solutions, but additional solutions may become non-dominated.
  • Adding constraints can either reduce or increase the cardinality of the Pareto-optimal set by changing which solutions remain feasible.

Orders and Pareto dominance

Orders formalize how solutions or objective vectors can be compared, including cases where elements are incomparable. Pareto order is a partial order on objective space and a preorder on search space, providing the structure for multiobjective optimization.

  • A binary relation is a set of ordered pairs from S × S, written x1Rx2 when (x1, x2) belongs to the relation.
  • A preorder is reflexive and transitive, while a partial order additionally satisfies antisymmetry.
  • Incomparability means that neither x1 ⪯pre x2 nor x2 ⪯pre x1 holds.
  • Minimal elements are not preceded by any other element, whereas maximal elements do not precede any other element.
  • For finite non-empty sets, at least one minimal and one maximal element exist; infinite preordered sets may have none.
  • Pareto order is a partial order on objective space but generally only a preorder on search space.

Exercises

The exercises apply binary relations, partial orders, cone orders, and Pareto order to concrete mathematical structures and physical interpretations.

  • The exercises ask readers to identify real-life binary relations and determine which axioms they satisfy.
  • They ask for an axiomatic characterization distinguishing incomparability from indifference.
  • One exercise represents the Pareto order on three-dimensional hypercube edges using a binary-relation graph and Hasse diagram.
  • Another exercise proves partial ordering under divisibility on N\{1} and identifies its minimal and maximal elements.
  • Cone-order exercises test point inclusion, Hasse-diagram construction, convexity of the Minkowski time cone, and photon co-location conditions.

Landscape Analysis

This section introduces Pareto landscapes through search-space neighborhoods, objective-space orders, and efficient-solution concepts. It also characterizes Pareto fronts and shows how level sets and constraints shape efficient solutions.

  • Search Space vs. Objective Space: Pareto optimization separates the decision space S from the objective space Y, linked by a vector-valued function f and restricted to feasible solutions X.The objective image is Y = f(X), while neighborhood structure in S supports local optimality and algorithmic search.
  • Search Space vs. Objective Space: A poset-valued landscape combines a set, neighborhood system, vector height function, and partial order on objective values.In finite spaces, the neighborhood graph describes search-space adjacency and the Hasse diagram represents objective-space ordering.
  • Efficiency and Weak Efficiency: The Pareto front contains non-dominated objective vectors, while the efficient set is their pre-image and may contain multiple solutions with the same objective vector.Efficiency is relative to the solution set being considered, including temporary algorithm-generated samples.
  • Efficiency and Weak Efficiency: Weakly efficient solutions exclude strict domination and can include boundary points that are not efficient; every efficient solution is weakly efficient.In the illustrated example, two points are efficient, while additional bold line segments represent weakly efficient solutions.
  • Pareto Fronts and Constraints: For linear problems with level curves intersecting at one point, efficient solutions may occur on constraint boundaries even when none exist in the unconstrained case.This highlights how constraints can create efficient solutions at boundary locations.
  • Pareto Fronts and Constraints: Pareto fronts with m objectives are subsets of, or equal to, (m−1)-dimensional manifolds.The chapter also uses level sets to analyze multicriteria landscapes and examines discrete landscapes with barrier trees.

Exercises

The exercises apply multicriteria optimization concepts to continuous, integer, and constrained problems. They ask readers to identify efficient or locally efficient solutions, visualize Pareto fronts, and use flooding for barrier analysis.

  • Continuous Problems: One exercise asks readers to identify proper and strictly efficient points for a two-objective continuous problem and verify level-set theorems.The problem minimizes f1(x) = x^2 and f2(x) = (x−1)^2 over x ∈ [0, 2].
  • Discrete Problems: The integer knapsack exercise combines maximizing f1(x) = 2x1 + 3x2 with minimizing f2(x) = x1 + 2x2 for x1, x2 ∈ {0, 1, 2, 3}.It asks for locally efficient points and a Pareto-front diagram with opposing objective directions.
  • Discrete Problems: The same knapsack exercise includes a bonus task to construct a barrier tree using the flooding algorithm with MAXWEIGHT = 10.This connects discrete multicriteria optimization with landscape-structure analysis.
  • Constrained Problems: A constrained exercise asks readers to graph the feasible region, test two candidate points for Pareto efficiency, and determine all efficient points or regions.The solution is guided by visualizing level-set improvements for both objectives.

Optimality conditions for differentiable problems

For differentiable optimization, local optimality is characterized through gradients, Hessians, existence results, and multiplier conditions for constraints. In multiobjective settings, KKT stationarity and Pareto efficiency need not yield an optimizer of a weighted-sum scalarization.

  • Unconstrained optimization: For unconstrained differentiable minimization, ∇f(x*) = 0 is necessary for a local extremum, while a positive (semi)definite Hessian provides a sufficient local-minimum condition.Stationary points satisfy the gradient condition; Hessian eigenvalues can test positive (semi)definiteness.
  • Global optimality: The Weierstrass theorem guarantees that a continuous function attains global maximum and minimum values on a closed and bounded subset of R^n.This existence result supports global-optimum conclusions when the feasible set is closed and bounded.
  • Equality constraints: For equality-constrained problems, Lagrange multipliers identify candidate optima by requiring a nontrivial multiplier combination of objective and constraint gradients.With λ1 set to 1, the multiplier equations form a system with m+n unknowns and m+n equations.
  • Equality constraints: At a constrained tangential optimum, the objective and constraint gradients are collinear, so their level curves share the same tangent line.This gives geometric intuition for the Lagrange multiplier condition.
  • Equality constraints: For one equality-constrained example, Weierstrass guarantees existence and the Lagrange conditions identify the only local minimum, which is therefore global.The feasible set is bounded and closed, and the objective is continuous.
  • Multiple objectives: In the multiobjective example, the candidate (2, 2) satisfies KKT conditions but is a saddle point, so equal-weight linear scalarization has no local minimizer.The Hessian is indefinite, with one positive and one negative eigenvalue.

Exercises

The exercises apply gradient, Hessian, Lagrange multiplier, graphical constraint, and KKT techniques to concrete unconstrained, constrained, and multiobjective problems.

  • Gradient-based unconstrained optimization: The cylinder exercise minimizes surface area for a fixed volume by substituting the volume constraint and analyzing the resulting one-variable objective.The formulation uses V(h,r) = πr^2h and S(h,r) = 2πr^2 + 2πrh.
  • Constrained and unconstrained problems: Several exercises ask students to derive gradients and Hessians, solve Lagrange multiplier problems, and analyze constrained regions graphically.Applications include a quadratic minimization, the closest point on Earth to a satellite, and feasibility checks at specified points.
  • KKT conditions for multiobjective optimization: The multiobjective exercises use KKT conditions to show that points on the segment t*(1, 1)^T, t ∈ [0, 1], are efficient.The task explicitly concerns an unconstrained two-objective minimization problem.

Scalarization Methods

Scalarization converts multicriteria optimization into a single aggregated objective, while Pareto methods seek sets of interesting solutions. The section compares weighted sums, utility functions, and distance-to-reference-point methods, emphasizing their coverage and limitations.

  • Overview: Scalarization aggregates multiple objectives into one objective through weighted sums or more general utility functions.These approaches raise questions about efficiency, Pareto-front coverage, and how weights control the resulting solution.
  • Linear Aggregation: 47?
  • Linear Aggregation: Properly efficient points have bounded trade-offs and, for cone-convex Pareto fronts, can be obtained using strictly positive weighted-sum coefficients.Proper efficiency is characterized by a bounded trade-off parameter in the bi-criterion case.
  • Linear Aggregation: Linear aggregation obtains every Pareto-front point for cone-convex fronts, but may return only boundary extremes on concave fronts.Its effectiveness therefore depends on the geometry of the Pareto front.
  • Utility and Reference-Point Methods: Monotone utility functions are designed so that optimizing utility leads to Pareto-optimal solutions, while distance methods target solutions near a reference point.The utility-function framework includes component value functions and preference-elicitation methods for constructing utilities.
  • Utility and Reference-Point Methods: The weighted Chebyshev distance is exhaustive, obtaining all Pareto-front points, but it can also produce weakly dominated points.Augmentation adds a small positive term to mitigate this issue; reference-point methods also depend on the target, metric, weights, and γ.
  • Approximation and Conclusions: Reference-point approximation is easier to control than gradually changing weighted-scalarization weights, but requires ideal and Nadir points, whose computation can be difficult.Some grid-based methods also incur effort that grows exponentially with the number of objectives when resolution is fixed.
  • Approximation and Conclusions: Single-point scalarization methods often serve as building blocks for algorithms that compute an entire Pareto front or an approximation.Among scalarization techniques, the Chebyshev distance is identified as the only exhaustive method, while desirability functions support interpretable preference elicitation.

Exercises

The exercises apply scalarization and utility-function concepts to multicriteria decision problems, including linear weighting, Chebyshev distance, pairwise preferences, and desirability analysis.

  • Linear Aggregation: Linear weighting aggregates multiple objectives into a single objective using user-defined weights.
  • Keeney-Raiffa Utility Function Graphical Solution: Keeney-Raiffa utility analysis represents two attributes with scaling constants and normalized attribute utility functions calibrated from preference assessments.
  • Chebyshev Scalarization: Chebyshev scalarization uses positive weights and reference values to convert a multiobjective linear program into a single-objective linear program through min-max linearization.
  • Utility Function from Pairwise Comparisons: Pairwise preferences can define linear-programming constraints for additive utility weights, while robustness maximization can address non-unique valid solutions.
  • Designing Desirability Functions for Decision Analysis: Desirability analysis structures a decision problem by specifying alternatives, criteria, constraints, preference-based desirability functions, objective importance, and Pareto-front comparisons.
  • Designing Desirability Functions for Decision Analysis: The exercises ask users to compute and visualize the Pareto front, compare resulting rankings with intuitive rankings, and examine how utility choices affect decisions.

Efficient computation of the non-dominated set

The section develops efficient methods for computing nondominated sets, contrasting general quadratic comparison complexity with faster geometric and Pareto-order algorithms. It presents sweep and divide-and-conquer procedures for low- and higher-dimensional cases.

  • General Complexity: Finding minimal or maximal elements in a general partially ordered set has time complexity Θ(n^2).
  • Geometric Pareto Order: For Pareto order in two or three dimensions, the KLP complexity bound is O(n log n).
  • Two- and Three-Dimensional Algorithms: The two-dimensional algorithm sorts points by one coordinate and maintains a maximal set using one comparison per update after sorting.
  • Two- and Three-Dimensional Algorithms: In three dimensions, balanced binary-tree maintenance supports efficient updates while the third coordinate is also sorted or represented through maximal subsets.
  • Higher-Dimensional Divide-and-Conquer: For dimensions d≥4, KLP uses divide-and-conquer: sort by the first coordinate, partition into R and S, recursively compute maxima, and filter dominated vectors.
  • Higher-Dimensional Divide-and-Conquer: The final maxima set combines the nondominated subset of R with vectors in the nondominated subset of S that are not dominated by R.

How to Efficiently Determine T

The computation of T filters the nondominated vectors in S against those in R after recursive partitioning. The merge is reduced to a lower-dimensional dominance problem and analyzed with a recurrence.

  • Merge Reduction: The merge exploits coordinate ordering: some cross-partition comparisons are settled by the first coordinate, leaving a d−1-dimensional problem for the remaining candidates.
  • Complexity Recurrence: The comparison cost for computing T is represented by a recurrence involving subproblems in dimensions d and d−1.
  • Exercises: The exercises ask learners to explain the merge, partition an eight-point four-dimensional set, compute nondominated subsets, and justify the final merge.

Evolutionary Multiobjective Optimization

Evolutionary multiobjective optimization uses population-based stochastic search to approximate well-distributed Pareto solutions, with selection paradigms balancing dominance, indicators, decomposition, and diversity.

  • Evolutionary Algorithms: Evolutionary algorithms evolve populations of candidate solutions for difficult nonlinear, nonconvex, nonsmooth, or gradient-free problems, but provide approximations rather than guaranteed optima.They efficiently explore complex search spaces but do not ensure optimality.
  • MOEAs: Multi-objective evolutionary algorithms seek well-distributed Pareto solutions, requiring selection schemes distinct from single-objective optimization.Their principal design differences lie in selection operators, while variation operators depend on the problem.
  • MOEA Design Paradigms: MOEAs follow Pareto-based, indicator-based, or decomposition-based paradigms that respectively prioritize dominance and diversity, performance indicators, or scalarized subproblems.Representative methods include NSGA-II and SPEA2, SMS-EMOA, and MOEA/D and NSGA-III.
  • Representative Algorithms: The tutorial presents NSGA-II, SMS-EMOA, and MOEA/D while discussing their design choices and deviations among related algorithms.The stated focus is on typical algorithms from each major paradigm.
  • NSGA-II: NSGA-II repeatedly varies a population, merges parents and offspring, then selects the μ best individuals using non-dominated sorting followed by crowding distance.The loop continues until a termination criterion such as convergence or a computational budget is reached.
  • NSGA-II: Crowding distance favors solutions with more surrounding objective-space area, helping preserve diversity among mutually non-dominated solutions.Its objective-wise contributions are determined by neighboring objective values within a nondominated layer.
  • Performance Indicators: The hypervolume indicator is complete and weakly compatible, while no unary indicator is both complete and compatible.The binary ε-indicator can determine whether one approximation set is better than another under its stated properties, unlike hypervolume values alone.
  • Many-objective Optimization: Many-objective optimization addresses the challenges of optimization with more than three objectives.The supplied passage identifies the setting and its challenges but does not enumerate them.

Exact Methods for Finding Pareto Optimal Sets

Exact methods compute or systematically explore Pareto optimal sets using deterministic mathematical techniques, while Bayesian optimization targets expensive black-box evaluations and MOLP exploits linear structure.

  • Overview: Exact methods deterministically enumerate or compute Pareto optimal points, complementing heuristic approaches such as evolutionary algorithms.The chapter briefly surveys homotopy, continuation, multiobjective linear programming, and Newton-Raphson approaches.
  • Homotopy and Continuation: Homotopy and continuation methods trace solution paths from an initial problem or across parameter spaces to explore Pareto fronts systematically.They are useful for nonlinear problems with non-convexity or disconnected Pareto sets.
  • Multiobjective Linear Programming: MOLP methods transform linear multiobjective problems into sequences of single-objective optimizations using weighted sums or ε-constraints.Benson’s method and dual-based algorithms support efficient Pareto-front generation.
  • Newton-Raphson Methods: Hypervolume-based Newton-Raphson methods iteratively use hypervolume gradients and Hessians to refine solutions toward Pareto optimality.Second-order information supports fast convergence for continuous problems with smooth trade-off surfaces.
  • Bayesian Multicriteria Global Optimization: Bayesian optimization models expensive black-box objectives probabilistically and balances exploration with exploitation.ParEGO uses Gaussian-process regression for scalarized objectives, while HVEI selects points by expected hypervolume improvement.
  • Geometric and Computational Exercises: The chapter exercises exact-method foundations through hypervolume gradients, MOLP geometry, and tangent-based continuation near efficient solutions.The exercises ask about dominated points’ gradient components and geometric properties of Pareto fronts and efficient sets.
Loading 2407.00359v6…