In
multi-objective optimization
Multi-objective optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, multiattribute optimization or Pareto optimization) is an area of multiple criteria decision making that is concerned with ...
, the Pareto front (also called Pareto frontier or Pareto curve) is the set of all
Pareto efficient
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engin ...
solutions. The concept is widely used in
engineering
Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more speciali ...
. 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.
Definition
The Pareto frontier, ''P''(''Y''), may be more formally described as follows. Consider a system with function
, where ''X'' is a
compact set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i. ...
of feasible decisions in the
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
, and ''Y'' is the feasible set of criterion vectors in
, such that
.
We assume that the preferred directions of criteria values are known. A point
is preferred to (strictly dominates) another point
, written as
. The Pareto frontier is thus written as:
:
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
In economics, the marginal rate of substitution (MRS) is the rate at which a consumer can give up some amount of one good in exchange for another good while maintaining the same level of utility. At equilibrium consumption levels (assuming no exte ...
is the same for all consumers. A formal statement can be derived by considering a system with ''m'' consumers and ''n'' goods, and a utility function of each consumer as
where
is the vector of goods, both for all ''i''. The feasibility constraint is
for
. To find the Pareto optimal allocation, we maximize the
Lagrangian
Lagrangian may refer to:
Mathematics
* Lagrangian function, used to solve constrained minimization problems in optimization theory; see Lagrange multiplier
** Lagrangian relaxation, the method of approximating a difficult constrained problem with ...
:
:
where
and
are the vectors of multipliers. Taking the partial derivative of the Lagrangian with respect to each good
for
and
and gives the following system of first-order conditions:
:
:
where
denotes the partial derivative of
with respect to
. Now, fix any
and
. The above first-order condition imply that
:
Thus, in a Pareto-optimal allocation, the marginal rate of substitution must be the same for all consumers.
Computation
Algorithms
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for computing the Pareto frontier of a finite set of alternatives have been studied in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
and power engineering. They include:
* "The maximum vector problem" or the
skyline query.
* "The scalarization algorithm" or the method of weighted sums.
* "The
-constraints method".
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. 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, last=Zitzler, first=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.
References
External links
* Code to compute the Pareto front of a finite set of points in Julia: https://github.com/cossio/ParetoEfficiency.jl.
Power engineering
Pareto efficiency