📂Optimization

Pareto Front

Definition

Let the objective function $\mathbf{f} : \mathbb{R}^{n} \to \mathbb{R}^{m}$ of the multiobjective optimization problem be representable, with respect to $f_{k} : \mathbb{R}^{n} \to \mathbb{R}$, as the following vector-valued function. $$ \mathbf{f} \left( \mathbf{x} \right) = \left( f_{1} \left( \mathbf{x} \right) , f_{2} \left( \mathbf{x} \right) , \cdots , f_{m} \left( \mathbf{x} \right) \right) $$

Simple definition

The set of solutions for which no superior (compatible) solution exists is called the Pareto front. In other words, it is defined as the set of solutions that are never useful to replace by any other solution.

Formal definition

Assume the optimization goal is to maximize each component of $f_{k}$. In the image (range) of $\mathbf{f}$, function value vectors $\mathbf{y} = \left( y_{1} , \cdots , y_{m} \right) = \mathbf{f} \left( \mathbf{x} \right)$ may be ordered as follows. $$ \mathbf{y} ' \prec \mathbf{y} '' \iff y_{k} ' < y_{k} '' , \forall k \in \left\{ 1, \cdots , m \right\} $$ If in every component $\mathbf{y} ''$ is greater than $\mathbf{y} '$, we say $\mathbf{y} ''$ dominates $\mathbf{y} '$. Let the set of feasible solutions be $X$; the Pareto front $P(Y)$ of $Y = \mathbf{f} (X)$ is then defined as the following set. $$ P(Y) = Y \setminus \left\{ \mathbf{y} \in Y : \exists \mathbf{y} ' \in Y , \mathbf{y} \prec \mathbf{y} ' \right\} $$ Equivalently, the Pareto front is the set of solutions for which there does not exist any solution that dominates them.

Explanation

According to the formal definition, solutions on the Pareto front satisfy the following. $$ \mathbf{y} ' , \mathbf{y} '' \in P(Y) \implies \mathbf{y} ' \nprec \mathbf{y} '' $$ Saying that they are the set of solutions not dominated by any other solution means, informally, that they have distinct, non-substitutable utility. Whether they are better or worse is secondary; at least for a given use, this collects only those solutions that are not inferior to anyone.

The figure makes the notion of a Pareto front much easier to understand. In the following figure, each point denotes a solution, and $y_{1}$ and $y_{2}$ are both assumed to be larger-is-better.

Here the red points belong to the Pareto front, and the others do not. The front is literally a front line: among the solution set, it forms the locus of solutions that are at least “not useless.”

• A and E are the most specialized solutions in $y_{2}$ and $y_{1}$, respectively. If you want to optimize even a single objective more than a balanced solution, choosing these is reasonable.
• B, C, and D on the Pareto front are relatively balanced. There is no single correct choice among them. If $y_{2}$ is more important, pick B; if $y_{1}$ is more important, pick D.
• H is dominated by A, B, C, and D. It is not better than any of them in any respect, so there is no reason to use H. Compared with E, H has a higher $y_{2}$, but since C, which is right nearby, is superior to E in every respect, choosing E is reasonable.
• Although H dominates G, that fact is meaningless. As long as C exists, how many other solutions a solution dominates is irrelevant. No matter how many solutions it dominates, the moment there exists a solution that dominates it, it loses significance.
• J, in terms of $y_{1}$ alone, is better than all other solutions except E, but it is dominated by E, so it is meaningless. It is better to use E than J.

Pareto optimality

In economics, a Pareto improvement is a change that makes someone better off without making anyone worse off, and a state is Pareto optimal if any improvement to one component necessarily worsens another. This notion corresponds to solutions on the Pareto front and intrinsically embodies a trade-off.

First front, second front, and the n-th front

The following figure is taken from the reference; although the axis directions are reversed, it is essentially the same idea¹.

By the definition of Pareto ranking, solutions can be ordered according to how close they are to the Pareto front. A simple procedure is to remove the Pareto front from the solution set and then find the next Pareto front. If $P_{1} (Y) = P(Y)$ is called the first front, then the $k$-th front is defined recursively as follows. $$ P_{k} (Y) = P \left( Y \setminus P_{k-1} (Y) \right) $$