Pareto front

The Pareto frontier, P(Y), may be more formally described as follows. Consider a system with function $f:\; X\; \backslash rightarrow\; \backslash mathbb\{R\}^m$, where X is a compact set of feasible decisions in the metric space $\backslash mathbb\{R\}^n$, and Y is the feasible set of criterion vectors in $\backslash mathbb\{R\}^m$, such that $Y\; =\; \backslash \{\; y\; \backslash in\; \backslash mathbb\{R\}^m:\backslash ;\; y\; =\; f(x),\; x\; \backslash in\; X\backslash ;\backslash \}$.

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

: $P(Y)\; =\; \backslash \{\; y^\backslash prime\; \backslash in\; Y:\; \backslash ;\; \backslash \{y^\{\backslash prime\backslash prime\}\; \backslash in\; Y:\backslash ;\; y^\{\backslash prime\backslash prime\}\; \backslash succ\; y^\{\backslash prime\},\; y^\backslash prime\; \backslash neq\; y^\{\backslash prime\backslash prime\}\; \backslash ;\; \backslash \}\; =\; \backslash empty\; \backslash \}.$

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.{{Cite book|last=Just, Richard E.|url=https://www.worldcat.org/oclc/58538348|title=The welfare economics of public policy : a practical approach to project and policy evaluation|publisher=E. Elgar|others=Hueth, Darrell L., Schmitz, Andrew.|year=2004|isbn=1-84542-157-4|location=Cheltenham, UK|pages=18–21|oclc=58538348}} 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=f^i(x^i)$ where $x^i=(x\_1^i,\; x\_2^i,\; \backslash ldots,\; x\_n^i)$ is the vector of goods, both for all i. The feasibility constraint is $\backslash sum\_\{i=1\}^m\; x\_j^i\; =\; b\_j$ for $j=1,\backslash ldots,n$. To find the Pareto optimal allocation, we maximize the Lagrangian:

: $L\_i((x\_j^k)\_\{k,j\},\; (\backslash lambda\_k)\_k,\; (\backslash mu\_j)\_j)=f^i(x^i)+\backslash sum\_\{k=2\}^m\; \backslash lambda\_k(z\_k-\; f^k(x^k))+\backslash sum\_\{j=1\}^n\; \backslash mu\_j\; \backslash left(\; b\_j-\backslash sum\_\{k=1\}^m\; x\_j^k\; \backslash right)$

where $(\backslash lambda\_k)\_k$ and $(\backslash mu\_j)\_j$ are the vectors of multipliers. Taking the partial derivative of the Lagrangian with respect to each good $x\_j^k$ for $j=1,\backslash ldots,n$ and $k=1,\backslash ldots,\; m$ gives the following system of first-order conditions:

: $\backslash frac\{\backslash partial\; L\_i\}\{\backslash partial\; x\_j^i\}\; =\; f\_\{x^i\_j\}^1-\backslash mu\_j=0\backslash text\{\; for\; \}j=1,\backslash ldots,n,$

: $\backslash frac\{\backslash partial\; L\_i\}\{\backslash partial\; x\_j^k\}\; =\; -\backslash lambda\_k\; f\_\{x^k\_j\}^i-\backslash mu\_j=0\; \backslash text\{\; for\; \}k=\; 2,\backslash ldots,m\; \backslash text\{\; and\; \}j=1,\backslash ldots,n,$

where $f\_\{x^i\_j\}$ denotes the partial derivative of $f$ with respect to $x\_j^i$. Now, fix any $k\backslash neq\; i$ and $j,s\backslash in\; \backslash \{1,\backslash ldots,n\backslash \}$. The above first-order condition imply that

: $\backslash frac\{f\_\{x\_j^i\}^i\}\{f\_\{x\_s^i\}^i\}=\backslash frac\{\backslash mu\_j\}\{\backslash mu\_s\}=\backslash 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|date=July 2020}}

Algorithms for computing the Pareto frontier of a finite set of alternatives have been studied in computer science and power engineering.{{cite journal|last1=Tomoiagă|first1=Bogdan|last2=Chindriş|first2=Mircea|last3=Sumper|first3=Andreas|last4=Sudria-Andreu|first4=Antoni|last5=Villafafila-Robles|first5=Roberto|year=2013|title=Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II|journal=Energies|volume=6|issue=3|pages=1439–55|doi=10.3390/en6031439|doi-access=free|hdl=2117/18257|hdl-access=free}} They include:

• "The maxima of a point set"
• "The maximum vector problem" or the skyline query{{cite journal|last1=Nielsen|first1=Frank|year=1996|title=Output-sensitive peeling of convex and maximal layers|journal=Information Processing Letters|volume=59|issue=5|pages=255–9|citeseerx=10.1.1.259.1042|doi=10.1016/0020-0190(96)00116-0}}{{cite journal|last1=Kung|first1=H. T.|last2=Luccio|first2=F.|last3=Preparata|first3=F.P.|year=1975|title=On finding the maxima of a set of vectors|journal=Journal of the ACM|volume=22|issue=4|pages=469–76|doi=10.1145/321906.321910|s2cid=2698043|doi-access=free}}{{cite journal|last1=Godfrey|first1=P.|last2=Shipley|first2=R.|last3=Gryz|first3=J.|year=2006|title=Algorithms and Analyses for Maximal Vector Computation|journal=VLDB Journal|volume=16|pages=5–28|citeseerx=10.1.1.73.6344|doi=10.1007/s00778-006-0029-7|s2cid=7374749}}
• "The scalarization algorithm" or the method of weighted sums{{cite journal|last1=Kim|first1=I. Y.|last2=de Weck|first2=O. L.|year=2005|title=Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation|journal=Structural and Multidisciplinary Optimization|volume=31|issue=2|pages=105–116|doi=10.1007/s00158-005-0557-6|issn=1615-147X|s2cid=18237050}}{{cite journal|last1=Marler|first1=R. Timothy|last2=Arora|first2=Jasbir S.|year=2009|title=The weighted sum method for multi-objective optimization: new insights|journal=Structural and Multidisciplinary Optimization|volume=41|issue=6|pages=853–862|doi=10.1007/s00158-009-0460-7|issn=1615-147X|s2cid=122325484}}
• "The $\backslash epsilon$-constraints method"{{cite journal|year=1971|title=On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization|journal=IEEE Transactions on Systems, Man, and Cybernetics|volume=SMC-1|issue=3|pages=296–297|doi=10.1109/TSMC.1971.4308298|issn=0018-9472}}{{cite journal|last1=Mavrotas|first1=George|year=2009|title=Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems|journal=Applied Mathematics and Computation|volume=213|issue=2|pages=455–465|doi=10.1016/j.amc.2009.03.037|issn=0096-3003}}{{cite journal |last1=Carvalho |first1=Iago A. |last2=Coco |first2=Amadeu A. |title=On solving bi-objective constrained minimum spanning tree problems |journal=Journal of Global Optimization |date=September 2023 |volume=87 |issue=1 |pages=301–323 |doi=10.1007/s10898-023-01295-8}}
• Multi-objective Evolutionary Algorithms {{cite journal |last1=Zhang |first1=Qingfu |last2=Hui |first2=Li |title=MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition |journal=IEEE Transactions on Evolutionary Computation |date=December 2007 |volume=11 |issue=6 |pages=712–731 |doi=10.1109/TEVC.2007.892759}}{{cite journal |last1=Carvalho |first1=Iago A. |last2=Ribeiro |first2=Marco A. |title=A node-depth phylogenetic-based artificial immune system for multi-objective Network Design Problems |journal=Swarm and Evolutionary Computation |date=November 2019 |volume=50 |page=100491 |doi=10.1016/j.swevo.2019.01.007}}

Since generating the entire Pareto front is often computationally-hard, there are algorithms for computing an approximate Pareto-front. For example, Legriel et al.{{Cite book|last1=Legriel|first1=Julien|last2=Le Guernic|first2=Colas|last3=Cotton|first3=Scott|last4=Maler|first4=Oded|date=2010|editor-last=Esparza|editor-first=Javier|editor2-last=Majumdar|editor2-first=Rupak|chapter=Approximating the Pareto Front of Multi-criteria Optimization Problems|title=Tools and Algorithms for the Construction and Analysis of Systems|series=Lecture Notes in Computer Science|volume=6015 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=69–83|doi=10.1007/978-3-642-12002-2_6|isbn=978-3-642-12002-2|doi-access=free}} 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{{Citation|last1=Zitzler|first1=Eckart|title=Quality Assessment of Pareto Set Approximations|date=2008|url=https://doi.org/10.1007/978-3-540-88908-3_14|work=Multiobjective Optimization: Interactive and Evolutionary Approaches|pages=373–404|editor-last=Branke|editor-first=Jürgen|series=Lecture Notes in Computer Science|place=Berlin, Heidelberg|publisher=Springer|language=en|doi=10.1007/978-3-540-88908-3_14|isbn=978-3-540-88908-3|access-date=2021-10-08|last2=Knowles|first2=Joshua|last3=Thiele|first3=Lothar|editor2-last=Deb|editor2-first=Kalyanmoy|editor3-last=Miettinen|editor3-first=Kaisa|editor4-last=Słowiński|editor4-first=Roman}} compare several algorithms for Pareto-set approximations on various criteria, such as invariance to scaling, monotonicity, and computational complexity.

Category:Power engineering

Category:Pareto efficiency