Pareto front

Summarize Timeline Fact Check

The Pareto frontier, P(Y), may be more formally described as follows. Consider a system with function ${\displaystyle f:X\rightarrow \mathbb {R} ^{m}}$, where X is a compact set of feasible decisions in the metric space ${\displaystyle \mathbb {R} ^{n}}$, and Y is the feasible set of criterion vectors in ${\displaystyle \mathbb {R} ^{m}}$, such that ${\displaystyle Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}}$.

We assume that the preferred directions of criteria values are known. A point ${\displaystyle y^{\prime \prime }\in \mathbb {R} ^{m}}$ is preferred to (strictly dominates) another point ${\displaystyle y^{\prime }\in \mathbb {R} ^{m}}$, written as ${\displaystyle y^{\prime \prime }\succ y^{\prime }}$. The Pareto frontier is thus written as:

${\displaystyle P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.}$

Summarize Timeline Top Qs Fact Check

A significant aspect of the Pareto frontier in economics is that, at a Pareto-efficient allocation, the marginal rate of substitution is the same for all consumers.^[6] A formal statement can be derived by considering a system with m consumers and n goods, and a utility function of each consumer as ${\displaystyle z_{i}=f^{i}(x^{i})}$ where ${\displaystyle x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})}$ is the vector of goods, both for all i. The feasibility constraint is ${\displaystyle \sum _{i=1}^{m}x_{j}^{i}=b_{j}}$ for ${\displaystyle j=1,\ldots ,n}$. To find the Pareto optimal allocation, we maximize the Lagrangian:

${\displaystyle L_{i}((x_{j}^{k})_{k,j},(\lambda _{k})_{k},(\mu _{j})_{j})=f^{i}(x^{i})+\sum _{k=2}^{m}\lambda _{k}(z_{k}-f^{k}(x^{k}))+\sum _{j=1}^{n}\mu _{j}\left(b_{j}-\sum _{k=1}^{m}x_{j}^{k}\right)}$

where ${\displaystyle (\lambda _{k})_{k}}$ and ${\displaystyle (\mu _{j})_{j}}$ are the vectors of multipliers. Taking the partial derivative of the Lagrangian with respect to each good ${\displaystyle x_{j}^{k}}$ for ${\displaystyle j=1,\ldots ,n}$ and ${\displaystyle k=1,\ldots ,m}$ gives the following system of first-order conditions:

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ for }}j=1,\ldots ,n,}$

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{k}}}=-\lambda _{k}f_{x_{j}^{k}}^{i}-\mu _{j}=0{\text{ for }}k=2,\ldots ,m{\text{ and }}j=1,\ldots ,n,}$

where ${\displaystyle f_{x_{j}^{i}}}$ denotes the partial derivative of ${\displaystyle f}$ with respect to ${\displaystyle x_{j}^{i}}$. Now, fix any ${\displaystyle k\neq i}$ and ${\displaystyle j,s\in \{1,\ldots ,n\}}$. The above first-order condition imply that

${\displaystyle {\frac {f_{x_{j}^{i}}^{i}}{f_{x_{s}^{i}}^{i}}}={\frac {\mu _{j}}{\mu _{s}}}={\frac {f_{x_{j}^{k}}^{k}}{f_{x_{s}^{k}}^{k}}}.}$

Thus, in a Pareto-optimal allocation, the marginal rate of substitution must be the same for all consumers.^[7]

Algorithms for computing the Pareto frontier of a finite set of alternatives have been studied in computer science and power engineering.^[8] They include:

• "The maxima of a point set"
• "The maximum vector problem" or the skyline query^[9][10][11]
• "The scalarization algorithm" or the method of weighted sums^[12][13]
• "The ${\displaystyle \epsilon }$-constraints method"^[14][15][16]
• Multi-objective Evolutionary Algorithms ^[17][18]

Since generating the entire Pareto front is often computationally-hard, there are algorithms for computing an approximate Pareto-front. For example, Legriel et al.^[19] call a set S an ε-approximation of the Pareto-front P, if the directed Hausdorff distance between S and P is at most ε. They observe that an ε-approximation of any Pareto front P in d dimensions can be found using (1/ε)^d queries.

Zitzler, Knowles and Thiele^[20] compare several algorithms for Pareto-set approximations on various criteria, such as invariance to scaling, monotonicity, and computational complexity.

Since the early 2000s, several evolutionary algorithms have become standard tools for Pareto front approximation. The Non-dominated Sorting Genetic Algorithm II (NSGA‑II) introduced elitism and a crowding‑distance mechanism to maintain diversity,^[21] becoming one of the most widely cited MOEAs. Its extension, NSGA‑III,^[22] replaces the crowding‑distance with a reference‑point‑based selection to handle problems with four or more objectives. Another influential approach is MOEA/D (Multi‑objective Evolutionary Algorithm based on Decomposition),^[23] which decomposes a multi‑objective problem into a number of scalar subproblems and optimizes them simultaneously.

More recent developments include the Genetic Algorithm with Calibration Variables (GA‑PC).^[24] GA‑PC modifies the NSGA‑II framework by introducing auxiliary calibration variables that do not affect the objective functions but help the algorithm escape local optima and break symmetries in the search space. It has been applied to constrained resource allocation problems with conflicting criteria (e.g., latency, energy consumption, and load balancing) and has been shown to produce a larger number of feasible Pareto‑optimal solutions compared to standard algorithms on similar problem instances.