Pareto front

In multi-objective optimization, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all Pareto efficient solutions.<ref>proximedia. "Pareto Front". www.cenaero.be. Retrieved 2018-10-08.</ref> The concept is widely used in engineering.<ref>Goodarzi, E., Ziaei, M., & Hosseinipour, E. Z., Introduction to Optimization Analysis in Hydrosystem Engineering (Berlin/Heidelberg: Springer, 2014), pp. 111–148.</ref> 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.<ref>Jahan, A., Edwards, K. L., & Bahraminasab, M., Multi-criteria Decision Analysis, 2nd ed. (Amsterdam: Elsevier, 2013), pp. 63–65.</ref><ref>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.</ref>

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 <math>f: X \rightarrow \mathbb{R}^m</math>, where X is a compact set of feasible decisions in the metric space <math>\mathbb{R}^n</math>, and Y is the feasible set of criterion vectors in <math>\mathbb{R}^m</math>, such that <math>Y = \{ y \in \mathbb{R}^m:\; y = f(x), x \in X\;\}</math>.

We assume that the preferred directions of criteria values are known. A point <math>y^{\prime\prime} \in \mathbb{R}^m</math> is preferred to (strictly dominates) another point <math>y^{\prime} \in \mathbb{R}^m</math>, written as <math>y^{\prime\prime} \succ y^{\prime}</math>. The Pareto frontier is thus written as:

<math>P(Y) = \{ y^\prime \in Y: \; \{y^{\prime\prime} \in Y:\; y^{\prime\prime} \succ y^{\prime}, y^\prime \neq y^{\prime\prime} \; \} = \empty \}. </math>

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.<ref>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.</ref> A formal statement can be derived by considering a system with m consumers and n goods, and a utility function of each consumer as <math>z_i=f^i(x^i)</math> where <math>x^i=(x_1^i, x_2^i, \ldots, x_n^i)</math> is the vector of goods, both for all i. The feasibility constraint is <math>\sum_{i=1}^m x_j^i = b_j</math> for <math>j=1,\ldots,n</math>. To find the Pareto optimal allocation, we maximize the Lagrangian:

<math>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)</math>

where <math>(\lambda_k)_k</math> and <math>(\mu_j)_j</math> are the vectors of multipliers. Taking the partial derivative of the Lagrangian with respect to each good <math>x_j^k</math> for <math>j=1,\ldots,n</math> and <math>k=1,\ldots, m</math> gives the following system of first-order conditions:

<math>\frac{\partial L_i}{\partial x_j^i} = f_{x^i_j}^1-\mu_j=0\text{ for }j=1,\ldots,n,</math>

<math>\frac{\partial L_i}{\partial x_j^k} = -\lambda_k f_{x^k_j}^i-\mu_j=0 \text{ for }k= 2,\ldots,m \text{ and }j=1,\ldots,n,</math>

where <math>f_{x^i_j}</math> denotes the partial derivative of <math>f</math> with respect to <math>x_j^i</math>. Now, fix any <math>k\neq i</math> and <math>j,s\in \{1,\ldots,n\}</math>. The above first-order condition imply that

<math>\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}.</math>

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.<ref>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.</ref> They include:

• "The maxima of a point set"
• "The maximum vector problem" or the skyline query<ref>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.</ref><ref>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.</ref><ref>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.</ref>
• "The scalarization algorithm" or the method of weighted sums<ref name="Kimde Weck2005">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.</ref><ref name="MarlerArora2009">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.</ref>
• "The <math>\epsilon</math>-constraints method"<ref>"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.</ref><ref name="Mavrotas2009">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.</ref>
• 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.<ref>Legriel, Julien; Le Guernic, Colas; Cotton, Scott; Maler, Oded (2010). Esparza, Javier; Majumdar, Rupak (eds.). "Approximating the Pareto Front of Multi-criteria Optimization Problems". Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6015: 69–83. doi:10.1007/978-3-642-12002-2_6. ISBN 978-3-642-12002-2.</ref> 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<ref>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</ref> compare several algorithms for Pareto-set approximations on various criteria, such as invariance to scaling, monotonicity, and computational complexity.

References

<references />