Pareto front explained

In multi-objective optimization, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all Pareto efficient solutions.^[1] The concept is widely used in engineering.^[2] 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] [4]}

Definition

The Pareto frontier, P(Y), may be more formally described as follows. Consider a system with function

f: X → R ^{m} , where X is a compact set of feasible decisions in the metric space R ^{n} , and Y is the feasible set of criterion vectors in R ^{m} , such that Y = \{ y \in 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 R ^{m} is preferred to (strictly dominates) another point y ^{\prime} \in 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} ≠ y ^{\prime\prime} \} = \empty \}.

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

z ^{i(x} _{i = f} ^{i)} where x ^{i,} _{1} x ^{i,} _{2} \ldots, x ^{i)} _{n} is the vector of goods, both for all i. The feasibility constraint is \sum ^{m} _{i =1} x ^{i} _{j} = b _{j} for j =1 ,\ldots,n . To find the Pareto optimal allocation, we maximize the Lagrangian:L _{i((x} ^{k)} ^{k,j} , ( λ _{k)} _{k,} (\mu _{j)} ^{i(x} ^{j) = f} ^{m} ^{k =2} λ _{k(z} _{k-} f ^{k(x} ^{n} ^{j =1} \mu _{j} \left( b _{j-\sum} ^{m} ^{k =1} x ^{k} _{j} \right)

where

( λ _{k)} _{k} and (\mu _{j)} _{j} are the vectors of multipliers. Taking the partial derivative of the Lagrangian with respect to each good x ^{k} _{j} for j =1 ,\ldots,n and k =1 ,\ldots, m gives the following system of first-order conditions:(\partial L _{i})/(\partial x ^{i} _{j}) = f ^{1- \mu} _{j =0 for j =1 ,\ldots,n,} (\partial L _{i})/(\partial x ^{k} _{j}) = -λ _{k} f ^{i - \mu} _{j =0} for k = 2 ,\ldots,m and j =1 ,\ldots,n,

where

f _{x ^{i} _{j}} denotes the partial derivative of f with respect to x ^{i} _{j} . Now, fix any k ≠ i and j,s\in \{ 1 ,\ldots,n\} . The above first-order condition imply that(f ^{i} _{x ^{i} _{j}})/(= f ^{i} _{x ^{i} _{s}}) (\mu _{j})/(= \mu _{s}) (f ^{k} _{x ^{k} _{j}})/(f ^{k} _{x ^{k} _{s}}) .

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

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

\epsilon -constraints method"^{[12] [13]}

• Multi-objective Evolutionary Algorithms

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.^[14] 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.

References

1. Web site: proximedia. Pareto Front. 2018-10-08. www.cenaero.be. https://web.archive.org/web/20200226003108/https://www.cenaero.be/Page.asp?docid=27103&. 2020-02-26. dead.
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. Book: Just, Richard E.. The welfare economics of public policy : a practical approach to project and policy evaluation. E. Elgar. Hueth, Darrell L., Schmitz, Andrew.. 2004. 1-84542-157-4. Cheltenham, UK. 18–21. 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. 10.3390/en6031439. free. 2117/18257. free.
7. Nielsen. Frank. 1996. Output-sensitive peeling of convex and maximal layers. Information Processing Letters. 59. 5. 255–9. 10.1.1.259.1042. 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. 10.1145/321906.321910. 2698043. free.
9. Godfrey. P.. Shipley. R.. Gryz. J.. 2006. Algorithms and Analyses for Maximal Vector Computation. VLDB Journal. 16. 5–28. 10.1.1.73.6344. 10.1007/s00778-006-0029-7. 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. 10.1007/s00158-005-0557-6. 1615-147X. 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. 10.1007/s00158-009-0460-7. 1615-147X. 122325484.
12. 1971. 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. 10.1109/TSMC.1971.4308298. 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. 10.1016/j.amc.2009.03.037. 0096-3003.
14. Legriel. Julien. Le Guernic. Colas. Cotton. Scott. Maler. Oded. 2010. Esparza. Javier. Majumdar. Rupak. Approximating the Pareto Front of Multi-criteria Optimization Problems. Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. 6015 . en. Berlin, Heidelberg. Springer. 69–83. 10.1007/978-3-642-12002-2_6. 978-3-642-12002-2. free.