Pareto front

Pareto front

In multi-objective optimization, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all Pareto efficient solutions. ^[1] Colloquially, this means when there are many distinct factors to consider in an optimization problem, a Pareto front represents the set of solutions that are "equally good" overall, albeit by making different concessions and compromises. The concept is widely used in engineering. ^{[2] : 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. ^{[3] : 63–65  [4] : 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 ${\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 \}.}$

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. ^[5] 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.^{[ citation needed ]}

Computation

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

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

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. ^[17] 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 ^[18] compare several algorithms for Pareto-set approximations on various criteria, such as invariance to scaling, monotonicity, and computational complexity.

References

1. proximedia. "Pareto Front". www.cenaero.be. Archived from the original on 2020-02-26. Retrieved 2018-10-08.
2. Goodarzi, E., Ziaei, M., & Hosseinipour, E. Z., Introduction to Optimization Analysis in Hydrosystem Engineering (Berlin/Heidelberg: Springer, 2014), pp. 111–148.
3. Jahan, A., Edwards, K. L., & Bahraminasab, M., Multi-criteria Decision Analysis, 2nd ed. (Amsterdam: Elsevier, 2013), pp. 63–65.
4. Costa, N. R., & Lourenço, J. A., "Exploring Pareto Frontiers in the Response Surface Methodology", in G.-C. Yang, S.-I. Ao, & L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlin/Heidelberg: Springer, 2015), pp. 399–412.
5. Just, Richard E. (2004). The welfare economics of public policy : a practical approach to project and policy evaluation. Hueth, Darrell L., Schmitz, Andrew. Cheltenham, UK: E. Elgar. pp. 18–21. ISBN   1-84542-157-4. OCLC   58538348.
6. Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto (2013). "Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II". Energies. 6 (3): 1439–55. doi: 10.3390/en6031439 . hdl: 2117/18257 .
7. Nielsen, Frank (1996). "Output-sensitive peeling of convex and maximal layers". Information Processing Letters. 59 (5): 255–9. CiteSeerX   10.1.1.259.1042 . doi:10.1016/0020-0190(96)00116-0.
8. Kung, H. T.; Luccio, F.; Preparata, F.P. (1975). "On finding the maxima of a set of vectors". Journal of the ACM. 22 (4): 469–76. doi: 10.1145/321906.321910 . S2CID   2698043.
9. Godfrey, P.; Shipley, R.; Gryz, J. (2006). "Algorithms and Analyses for Maximal Vector Computation". VLDB Journal. 16: 5–28. CiteSeerX   10.1.1.73.6344 . doi:10.1007/s00778-006-0029-7. S2CID   7374749.
10. Kim, I. Y.; de Weck, O. L. (2005). "Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation". Structural and Multidisciplinary Optimization. 31 (2): 105–116. doi:10.1007/s00158-005-0557-6. ISSN   1615-147X. S2CID   18237050.
11. Marler, R. Timothy; Arora, Jasbir S. (2009). "The weighted sum method for multi-objective optimization: new insights". Structural and Multidisciplinary Optimization. 41 (6): 853–862. doi:10.1007/s00158-009-0460-7. ISSN   1615-147X. S2CID   122325484.
12. "On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization". IEEE Transactions on Systems, Man, and Cybernetics. SMC-1 (3): 296–297. 1971. doi:10.1109/TSMC.1971.4308298. ISSN   0018-9472.
13. Mavrotas, George (2009). "Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems". Applied Mathematics and Computation. 213 (2): 455–465. doi:10.1016/j.amc.2009.03.037. ISSN   0096-3003.
14. Carvalho, Iago A.; Coco, Amadeu A. (September 2023). "On solving bi-objective constrained minimum spanning tree problems". Journal of Global Optimization. 87 (1): 301–323. doi:10.1007/s10898-023-01295-8.
15. Zhang, Qingfu; Hui, Li (December 2007). "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition". IEEE Transactions on Evolutionary Computation. 11 (6): 712–731. doi:10.1109/TEVC.2007.892759.
16. Carvalho, Iago A.; Ribeiro, Marco A. (November 2019). "A node-depth phylogenetic-based artificial immune system for multi-objective Network Design Problems". Swarm and Evolutionary Computation. 50 100491. doi:10.1016/j.swevo.2019.01.007.
17. Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). "Approximating the Pareto Front of Multi-criteria Optimization Problems". In Esparza, Javier; Majumdar, Rupak (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Vol. 6015. Berlin, Heidelberg: Springer. pp. 69–83. doi: 10.1007/978-3-642-12002-2_6 . ISBN   978-3-642-12002-2.
18. Zitzler, Eckart; Knowles, Joshua; Thiele, Lothar (2008), Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.), "Quality Assessment of Pareto Set Approximations" , Multiobjective Optimization: Interactive and Evolutionary Approaches, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 373–404, doi:10.1007/978-3-540-88908-3_14, ISBN   978-3-540-88908-3 , retrieved 2021-10-08