# Pareto front

In multi-objective optimization, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all Pareto efficient solutions. The concept is widely used in engineering.: 111–148  It allows the designer to restrict attention to the set of efficient choices, and to make tradeoffs within this set, rather than considering the full range of every parameter.: 63–65 : 399–412 Example of a Pareto frontier. The boxed points represent feasible choices, and smaller values are preferred to larger ones. Point C is not on the Pareto frontier because it is dominated by both point A and point B. Points A and B are not strictly dominated by any other, and hence lie on the frontier. A production-possibility frontier. The red line is an example of a Pareto-efficient frontier, where the frontier and the area left and below it are a continuous set of choices. The red points on the frontier are examples of Pareto-optimal choices of production. Points off the frontier, such as N and K, are not Pareto-efficient, since there exist points on the frontier which Pareto-dominate them.

## Definition

The Pareto frontier, P(Y), may be more formally described as follows. Consider a system with function $f:X\rightarrow \mathbb {R} ^{m}$ , where X is a compact set of feasible decisions in the metric space $\mathbb {R} ^{n}$ , and Y is the feasible set of criterion vectors in $\mathbb {R} ^{m}$ , such that $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 $y^{\prime \prime }\in \mathbb {R} ^{m}$ is preferred to (strictly dominates) another point $y^{\prime }\in \mathbb {R} ^{m}$ , written as $y^{\prime \prime }\succ y^{\prime }$ . The Pareto frontier is thus written as:

$P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.$ ## Marginal rate of substitution

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. A formal statement can be derived by considering a system with m consumers and n goods, and a utility function of each consumer as $z_{i}=f^{i}(x^{i})$ where $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 $\sum _{i=1}^{m}x_{j}^{i}=b_{j}$ for $j=1,\ldots ,n$ . To find the Pareto optimal allocation, we maximize the Lagrangian:

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

${\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ for }}j=1,\ldots ,n,$ ${\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 $f_{x_{j}^{i}}$ denotes the partial derivative of $f$ with respect to $x_{j}^{i}$ . Now, fix any $k\neq i$ and $j,s\in \{1,\ldots ,n\}$ . The above first-order condition imply that

${\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.[citation needed]

## Computation

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

• "The maxima of a point set".
• "The maximum vector problem" or the skyline query.
• "The scalarization algorithm" or the method of weighted sums.
• "The $\epsilon$ -constraints method".

## Approximations

Since generating the entire Pareto front is often computationally-hard, there are algorithms for computing an approximate Pareto-front. For example, Legriel et al. 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 compare several algorithms for Pareto-set approximations on various criteria, such as invariance to scaling, monotonicity, and computational complexity.