# How do you compute the Pareto Front of a set?

I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst and chose based on which one finished higher but whats better 3rd and 2nd, or 1st and 4th?

Pareto front is a set of nondominated solutions, being chosen as optimal, if no objective can be improved without sacrificing at least one other objective.

1. (Energy Used, Weight)

(30,20)

(50,30)

(10,40)

(20,50)

(40,10)

Diagram Showing the Table

• Can you provide the definition of a Pareto Front? – Bryce Kille Apr 25 at 14:12
• Crossposted and answered at MSE (please don't do that): math.stackexchange.com/questions/3201977/… – Noah Schweber Apr 25 at 16:17
• @NoahSchweber apologies wasn't sure where to ask or relevance to either place. – MF DOOM Apr 25 at 16:52

## 1 Answer

A multi-objective optimization problem can be formulated as

\begin{align} \min\limits_{\phi \in \Phi} & \quad [f_1(\phi), f_2(\phi), \ldots, f_m(\phi)]^T \label{eq:mo-objectives} \\ s.t. & \quad g_j(\phi) \leqslant 0,~j = 1, \ldots, J \label{eq:mo-constraints} \end{align}

Without loss of generality, assume that all objective functions are minimization functions. In this problem, the first equation represents the set of $$m$$ objective functions and the second denotes the problem constraints, which generate a polytope $$\mathcal{P}$$. Furthermore, $$\Phi$$ denotes the set of feasible solutions contained in $$\mathcal{P}$$ and $$\phi \in \Phi$$ represents a feasible solution.

A solution $$\phi_1 \in \Phi$$ dominates another solution $$\phi_2 \in \Phi$$ if and only if $$f_i(\phi_1) \leqslant f_i(\phi_2)$$ for all objective functions $$\{f_1, f_2, \ldots, f_m\}$$ and $$f_i(\phi_1) < f_i(\phi_2)$$ for at least one objective function $$f_i$$.

A solution $$\phi' \in \Phi$$ is said to be non-dominated if and only if there is no solution $$\phi \in \Phi$$ such that $$\phi$$ dominates $$\phi'$$.

A non-dominated solution $$\phi^* \in \Phi$$ is said to be Pareto-optimal if and only if, for all solutions $$\phi \in \Phi$$, $$f_i(\phi^*) \leqslant f_i(\phi)$$ for all objective functions $$\{f_1, f_2, \ldots, f_m\}$$ and $$f_i(\phi^*) < f_i(\phi)$$ for at least one objective function $$f_i$$.

The Pareto-front is the set of the Pareto-optimal solutions.

We can derive a simple algorithm to compute the Pareto-front of a given subset of solutions $$\Phi' = \{\Phi'_1, \ldots, \Phi'_n\} \subseteq \Phi$$. This algorithm will be specifically designed for your case (two objectives), but can easily be generalized to any number $$m$$ of objective functions.

First of all, assume that the solutions in $$\Phi'$$ are ordered in increasing order of the first objective (energy used). In addition, ensure that, for a given value of energy used, the solutions are also ordered in increasing order of their second objective (weight).

1. Let $$i \gets 1$$.
2. Add $$\Phi'_i$$ to the Pareto-front.
3. Find smallest $$j>i$$ such that $$\operatorname{weight}(\Phi'_j) < \operatorname{weight}(\Phi'_i)$$.
4. If no such $$j$$ exists, stop. Otherwise let $$i \gets j$$ and go to step 2.